給出一個序列（長度>=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 }

?

總結

以上是生活随笔為你收集整理的【HDU 5532 Almost Sorted Array】水题，模拟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。