http://codeforces.com/contest/761/problem/B
题意:
有一个长度为l的环形跑道,跑道上有n个障碍,现在有2个人,给出他们每过多少米碰到障碍,判断他们跑的是不是同一个跑道。
思路:
如果是同一个跑道,那么障碍与障碍之间的距离是相同的。
所以我们可以先计算出两个人的跑道的障碍之间的距离,然后暴力比较,如果全部一样就是同一个跑道(因为是环形跑道,所以在比较的时候每次都需要将第一个加到最后)。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cstdio> 7 using namespace std; 8 9 int n,l; 10 int a[55],b[55]; 11 int A[55],B[55*2]; 12 13 int main() 14 { 15 //freopen("D:\input.txt", "r", stdin); 16 while(~scanf("%d%d",&n,&l)) 17 { 18 for(int i=0;i<n;i++) scanf("%d",&a[i]); 19 for(int i=0;i<n;i++) scanf("%d",&b[i]); 20 21 int sum=0; 22 for(int i=1;i<n;i++) 23 { 24 A[i-1]=a[i]-a[i-1]; 25 sum+=a[i]-a[i-1]; 26 } 27 A[n-1]=l-sum; 28 29 sum=0; 30 for(int i=1;i<n;i++) 31 { 32 B[i-1]=b[i]-b[i-1]; 33 sum+=b[i]-b[i-1]; 34 } 35 B[n-1]=l-sum; 36 37 bool flag=false; 38 for(int t=0;t<n;t++) 39 { 40 for(int i=0;i<n;i++) 41 { 42 if(A[i]!=B[(i+t)%n]) break; 43 if(i==n-1) flag=true; 44 } 45 if(flag) break; 46 } 47 if(flag) puts("YES"); 48 else puts("NO"); 49 } 50 return 0; 51 }