给出一个序列（长度>=2），问去掉一个元素后是否能成为单调不降序列或单调不增序列。
对任一序列，先假设其可改造为单调不降序列，若成立则输出YES，不成立再假设其可改造为单调不增序列，若成立则输出YES，不成立则输出NO。
由于持平不影响整体单调性，为了直观，我在以下把“不降”称为“递增/升序”，把“不增”称为“递减/降序”。
递增和递减是对称的，这里先考虑递增，递减改个符号和最值就好。
我们把为维护单调性而去掉的那个点称为“坏点”。由题目的要求，“可改造”可等价于“只存在一个坏点”。
对于“坏点”的判断，我们可以先找出是否只存在一组“逆序”。
对于“almosted sorted”递增序列，只存在一组逆序无非以下四种情况（这里先不考虑逆序在边界）。
现在考虑逆序在边界的情况。由于a[]数组元素下标是1~n，而此题1<=ai<=100000，那么对于递增序列，可把a[0]设为1、把a[n+1]设为100000作为首尾哨兵节点，一定不会破坏整体单调性；递减序列做对称的处理。这样边界也可以像中间一样处理。
由于三种情况满足一种即可，而第二种可以看作第三种和第四种的交集，故只需按照第三种和第四种的情况对a[]数组各进行一次遍历，满足一种即可输出YES。
对于坏点的处理，我们采用“当它不存在”的策略，所以首次遇到坏点，忽略它，再次遇到坏点，则此种情况不成立。
至于如何由“逆序”推出“坏点”，并实现几种情况的判断，我们遍历i:0~n，对于第一对逆序a[i]>a[i+1]，我们可以：
先采取“左归”（第三种），即把a[i]当作坏点，判断a[i-1]和a[i+1]是否升序（若不升序则相当于构成了第二对逆序，出现第二个坏点）；
若左归不成立，再采取“右归”（第四种），即把a[i+1]当坏点，同理判断a[i]和a[i+2]是否升序。
11.23更新代码如下，更加简化，速度更快
1 #include <cstdio>
2 using namespace std;
3
4 const int MAX_N=100005;
5 const int MIN_A=1;
6 const int MAX_A=100000;
7 int T;
8 int n;
9 int a[MAX_N];
10 int flag;
11 int fix_cnt;
12
13 int main()
14 {
15 freopen("5532.txt","r",stdin);
16 scanf("%d",&T);
17 while(T--)
18 {
19 scanf("%d",&n);
20 for(int i=1;i<=n;i++)
21 {
22 scanf("%d",&a[i]);
23 }
24 //升序
25 flag=1;//假设去掉最多一个元素后整体降序
26 fix_cnt=0;
27 a[0]=MIN_A;
28 a[n+1]=MAX_A;
29 for(int i=1;i<=n-1;i++)
30 {
31 if(a[i]<=a[i+1]) continue;
32 fix_cnt++;
33 if(fix_cnt<=1&&(a[i-1]<=a[i+1]||a[i]<=a[i+2])) continue;
34 flag=0;
35 break;
36 }
37 if(flag)
38 {
39 printf("YES\n");
40 continue;
41 }
42 //降序
43 flag=1;//假设去掉最多一个元素后整体降序
44 fix_cnt=0;
45 a[0]=MAX_A;
46 a[n+1]=MIN_A;
47 for(int i=1;i<=n-1;i++)
48 {
49 if(a[i]>=a[i+1]) continue;
50 fix_cnt++;
51 if(fix_cnt<=1&&(a[i-1]>=a[i+1]||a[i]>=a[i+2])) continue;
52 flag=0;
53 break;
54 }
55 if(flag)
56 {
57 printf("YES\n");
58 continue;
59 }
60 printf("NO\n");
61 }
62 return 0;
63 }
先前版本代码如下：
1 #include <cstdio>
2 using namespace std;
3
4 const int MAX_N=100005;
5 const int MIN_A=1;
6 const int MAX_A=100000;
7 int T;
8 int n;
9 int in[MAX_N],de[MAX_N];
10 int flag;
11 int fix_cnt;
12
13 int main()
14 {
15 freopen("5532.txt","r",stdin);
16 scanf("%d",&T);
17 while(T--)
18 {
19 scanf("%d",&n);
20 for(int i=1;i<=n;i++)
21 {
22 scanf("%d",&in[i]);
23 de[i]=in[i];
24 }
25
26 //升序的情况
27 in[0]=MIN_A;
28 in[n+1]=MAX_A;
29 flag=1;//假设去掉最多一个元素后整体升序
30 fix_cnt=0;
31 for(int i=1;i<=n-1;i++)
32 {
33 if(in[i]<=in[i+1]) continue;
34 fix_cnt++;//左归的情况
35 if(fix_cnt<=1&&in[i-1]<=in[i+1]) continue;
36 flag=0;
37 break;
38 }
39 if(flag)
40 {
41 printf("YES\n");
42 continue;
43 }
44 flag=1;
45 fix_cnt=0;
46 for(int i=1;i<=n-1;i++)
47 {
48 if(in[i]<=in[i+1]) continue;
49 fix_cnt++;//右归的情况
50 if(fix_cnt<=1&&in[i]<=in[i+2]) continue;
51 flag=0;
52 break;
53 }
54 if(flag)
55 {
56 printf("YES\n");
57 continue;
58 }
59 //降序的情况
60 de[0]=MAX_A;
61 de[n+1]=MIN_A;
62 flag=1;//假设去掉最多一个元素后整体降序
63 fix_cnt=0;
64 for(int i=1;i<=n-1;i++)
65 {
66 if(de[i]>=de[i+1]) continue;
67 fix_cnt++;//左归的情况
68 if(fix_cnt<=1&&de[i-1]>=de[i+1]) continue;
69 flag=0;
70 break;
71 }
72 if(flag)
73 {
74 printf("YES\n");
75 continue;
76 }
77 flag=1;
78 fix_cnt=0;
79 for(int i=1;i<=n-1;i++)
80 {
81 if(de[i]>=de[i+1]) continue;
82 fix_cnt++;//右归的情况
83 if(fix_cnt<=1&&de[i]>=de[i+2]) continue;
84 flag=0;
85 break;
86 }
87 if(flag)
88 {
89 printf("YES\n");
90 continue;
91 }
92 printf("NO\n");
93 }
94 return 0;
95 }