[Codeforces761B]Dasha and friends

题目传送门

题意

两个人逆时针绕长度为L的圈跑，并在n个点停留。由于起点不一样，所以到达这n个点的距离不一样，现在给定这两个人先后到达这n个点的距离，判断两人是否绕同一个圈跑。

Consider an example. Let L = 8, blue points are barriers, and green points are Kefa’s start (A) and Sasha’s start (B). Then Kefa writes down the sequence[2, 4, 6], and Sasha writes down [1, 5, 7].

思路

虽然起点不一样，但如果是同一个圈的话，这n个点的相对位置是一样的，既任意两点的最短距离一致。

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#define READ(x) scanf("%d",&x)
#define READLL(x) scanf("%lld",&x)
#define LL long long
#define MAXN
using namespace std;
int dis1[5000];
int dis2[5000];
int cnt1,cnt2;
int n;
int L;
int num[60];
int main(){
    int flag;
    int q;
    while(cin>>n>>L){
        cnt1 = cnt2 = 0;
        flag = 0;
        for(int i = 1;i <= n;i++) READ(num[i]);
        for(int i = 1;i <= n;i++){
            for(int j = i+1;j <= n;j++){
                q = min(abs(num[i]-num[j]),L-abs(num[i]-num[j]));
                dis1[++cnt1]=q;
            }
        }
        for(int i = 1;i <= n;i++) READ(num[i]);
        for(int i = 1;i <= n;i++){
            for(int j = i+1;j <= n;j++){
                q = min(abs(num[i]-num[j]),L-abs(num[i]-num[j]));
                dis2[++cnt2]=q;
            }
        }
        sort(dis1,dis1+cnt1+1);
        sort(dis2,dis2+cnt2+1);
        for (int i = 1;i<=cnt1;i++){
            if(dis1[i]!=dis2[i]){
                flag = 1;
                break;
            }
        }
        if(flag)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

留言

2017-02-01
⬆︎TOP