題目鏈接:http://codeforces.com/contest/451/problem/B
codeforces打不開、解題報告:給出一個序列,要你判斷這個序列能不能通過將其中某個子序列翻轉使其成為升序的序列。
我的做法有點不一樣,我是將原來的序列先按照升序排好序,然后分別從頭和尾開始掃,找到跟原來的數組不一樣的子序列的區間,然后判斷這個區間是不是原來的區間翻轉而來。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 typedef long long INT; 7 const int maxn = 100000+5; 8 INT que[maxn],que2[maxn]; 9 int main() 10 { 11 int n; 12 while(scanf("%d",&n)!=EOF) 13 { 14 for(int i = 1;i <= n;++i) 15 { 16 scanf("%lld",&que[i]); 17 que2[i] = que[i]; 18 } 19 sort(que+1,que+n+1); 20 int l = 1; 21 for(;l < n;++l) 22 if(que[l] == que[l+1]) 23 break; 24 if(l < n) 25 { 26 printf("no\n"); 27 continue; 28 } 29 int s = 1,e = n; 30 while(s <= n && que[s] == que2[s]) s++; 31 if(s > n) 32 { 33 printf("yes\n1 1\n"); 34 continue; 35 } 36 while(e >= 1 && que[e] == que2[e]) e--; 37 int x = s,y = e; 38 while(s <= y && que[s] == que2[e]) s++,e--; 39 printf(s > y? "yes\n%d %d\n":"no\n",x,y); 40 } 41 return 0; 42 }