Codeforces-1486A Shifting Stacks


Problem

Portal


Meaning

给定一个序列,每次将第i个数-1,第i+1个数+1,问是否能够将其变成严格单调递增的序列。


Thoughts

输出no的情况,当前数不够大,所以在前面我们尽可能的将当前数做到条件允许的最小值(0,1,2,…),同时将尽量多的数加到第i+1个数上,判断是否满足条件即可。


Accepted Code

#include <bits/stdc++.h>
#define endl '\n' 
#define int long long

using namespace std;

const int N = 1e4+10;

int h[N];

signed main()
{
    int T; cin >> T;
    while(T -- )
    {
        int n, flag = 0; cin >> n;
        for(int i = 0 ; i < n ; i ++ ) cin >> h[i];
        for(int i = 0 ; i < n ; i ++ )
        {
            int t = h[i] - i;
            if(t < 0) {flag = 1; break;}
            h[i+1] += t;
        }
        if(flag) puts("no");
        else puts("yes");
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Codeforces-1486B Eastern Exhibition Codeforces-1486B Eastern Exhibition
ProblemPortal Thoughts这个就是货仓选址那个题的经典结论:取所有x的中位数,如果n是奇数那么中位数唯一;反之可以选中间两个数之间的任何一个位置.那么由于两个子问题相互独立,直接乘法原理统计方案数就可以了. Accep
Next 
Codeforces-1490B Balanced Remainders Codeforces-1490B Balanced Remainders
ProblemPortal Meaning给三个数,求每次选择一个数-1,他的后一个数+1(第三个数的后一个数是第一个数),问最少需要多少步是的三个数相等。 Thoughts每次选最大的数-1。 Accepted Code#inclu
  TOC