t題目鏈接：http://codeforces.com/contest/1291/problem/B
思路：
用極端的情況去考慮問題，會變得很簡單，
無論是單調遞增，單調遞減，或者中間高兩邊低的情況都可以變為三種模型，
（1）0,1,2,3,4........n-3,n-2,n-1
（2）n-1,n-2,n-3.....3,2,1,0
（3）0,1,2,3,4,.....n.......4,3,2,1,0
那么，我們只需要查看當前位置是否大于等于極端模型（3）在這個位置的數值，如果當前位置不滿足了，
那么我們就讓當前位置和之后的數值去和極端模型（3）n后面遞減的數值去比較，如果還有不滿足的情況說明就是“NO”了，
注意一種情況 0 1 1 0需要特殊處理一下，
1 #include <iostream> 2 using namespace std; 3 4 const int N = (int)3e5+100; 5 int a[N]; 6 7 int main(){ 8 9 int T,n; 10 while(cin >> T){ 11 while(T--){ 12 cin >> n; 13 for(int i = 1; i <= n; ++i) cin >> a[i]; 14 int i; 15 bool ok = 1; 16 //遞增區間判斷 17 for(i = 1; i <= n; ++i){ 18 if(a[i] >= i-1) continue; 19 break; 20 } 21 // 0 1 1 0 這種情況判定 22 if(i <= n){ 23 if(a[i] == a[i-1] && !(a[i] >= n-i+1)) ok = 0; 24 } 25 //遞減區間判定 26 for(; i <= n; ++i){ 27 if(a[i] >= n-i) continue; 28 ok = 0; break; 29 } 30 //if(ok) cout << "----------Yes" << endl; 31 //else cout << "----------No" << endl; 32 if(ok) cout << "----------Yes" << endl; 33 else cout << "----------No" << endl; 34 } 35 } 36 37 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95256.html
標籤：其他
上一篇：求約數個數（模板）
下一篇：求約數之和