题目链接
AtCoder Beginner Contest 139
E
思路
这道题就是纯属暴力，不过学习到了，数组放在栈内比放在堆内跑的要快。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int main()
{
int n;
int a[maxn][maxn]={};
bool vis[maxn]={};
int now[maxn]={};
scanf("%d",&n);
for(int i=1;i<maxn;i++)now[i]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n-1;j++)
{
scanf("%d",&a[i][j]);
}
}
int day = 0;
int round = 0;
while(1)
{ memset(vis,false,sizeof(vis));
bool ok = false;
for(int j=1;j<=n;j++)
{
int b = a[j][now[j]];
if(now[j]>=n||vis[b]||vis[j])continue;
if(a[b][now[b]]==j)
{
ok = true;
now[j]++;
now[b]++;
vis[j]=true;
vis[b]=true;
round++;
if(round==n*(n-1)/2)return 0*printf("%d\n",day+1);
}
}
if(!ok)return 0*printf("-1\n");
day++;
}
return 0*printf("%d\n",day);
}
|
E
思路
每个移动的步数可以看成一个向量，那么每次移动的时候，选择角度离自己最小的可以了。
用极角排序后，维护最大值即可
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
double x,y;
bool operator < (const node b)
{
return atan2(y,x)<atan2(b.y,b.x);
}
}a[105];
int main()
{
int n;
double ans = 0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
double x=0,y=0;
int j = i;
do
{
x+=a[j].x;
y+=a[j].y;
ans=max(ans,sqrt(x*x+y*y));
j++;
j%=n;
}while(j!=i);
}
printf("%.15lf\n",ans);
}
|