Codeforces Round #616 (Div. 2) B. Array Sharpening

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需要特殊处理一下。

 #include <iostream>

 using namespace std;

 const int N = (int)3e5+;

 int a[N];

 int main(){

     int T,n;

     while(cin >> T){

         while(T--){

             cin >> n;

             for(int i = ; i <= n; ++i) cin >> a[i];

             int i;

             bool ok = ;

             //递增区间判断

             for(i = ; i <= n; ++i){

                 if(a[i] >= i-) continue;

                 break;

             }

             // 0 1 1 0 这种情况判定

             if(i <= n){

                 if(a[i] == a[i-] && !(a[i] >= n-i+)) ok = ;

             }

             //递减区间判定

             for(; i <= n; ++i){

                 if(a[i] >= n-i) continue;

                 ok = ; break;

             }

             //if(ok) cout << "----------Yes" << endl;

             //else cout << "----------No" << endl;

             if(ok) cout << "----------Yes" << endl;

             else cout << "----------No" << endl;

         }

     }

 }

巴特西

Codeforces Round #616 (Div. 2) B. Array Sharpening

最新文章

热门文章