题目链接:
1.luogu
2.codeforces

由于写题解的时候hack还未完毕。有没有FST将在评论里说明
本题解使用了is_sorted为C++11语法,若想查看C++98是怎么写的请移步其他人的题解

首先,我使用了双端队列,他可以pop_back(),pop_front(),push_back(),push_front(),且还可以下标访问,十分方便。
然后我们每输入一个数,就将他放入双端队列的末端
再循环n次,先查看是否是有序的,然后将最后一个数放到最前面来。如果碰到是有序的就输出YES,否则输出NO

解释一下,为什么用了两个is_sorted
首先,is_sorted默认是检查从小到大是否有序的,然而这道题目要求的是从小到大或者是从大到小都是可以的,所以先检查从小到大是否有序,再手写一个cmp函数,再检查从大到小是否有序。

代码:

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;
int q,n,p;
deque<int> dq,dq2;
bool cmp(const int &x,const int &y) {
return x>y;
}
int main() {
scanf("%d",&q);
while(q--) {
dq.clear();
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&p);
dq.push_back(p);
}
bool g=true;
for(int i=1;i<=n;i++) {
if(is_sorted(dq.begin(),dq.end())) {
printf("YES\n");
g=false;
break;
}
if(is_sorted(dq.begin(),dq.end(),cmp)) {
printf("YES\n");
g=false;
break;
}
p=dq.back();
dq.pop_back();
dq.push_front(p);
}
if(g) printf("NO\n");
}
return 0;
}

Note:C++11 在NOIP中并不支持,所以尽量少用