题解：AT_arc185_b [ARC185B] +1 and -1

· · 题解

题目大意

给定一个长度为 N 的序列，每次选取两个数，前者 +1 后者-1，问能否通过若干次操作使得序列不降。

解题思路

我们发现操作不会改变序列的和，那么试着将其平均分。

考虑一个不降的序列，其必然能继续进行若干次操作变为如下序列：

x,x,...,x,x+1,...,x+1,x+1

而不能变为不降的序列则不能。问题转化为原序列能否变为该序列。

遍历一遍原序列，只要前缀转化为目标序列的 +1 操作数始终大于 -1 操作数就可以。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,n,a[200005],b[200005],sum,r;
bool f;
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;sum=0;r=0;f=false;//多测不清空，爆零两行泪
        for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
        for(int i=1;i<=n;i++){b[i]=sum/n;if(i>(n-sum%n))b[i]++;}//求目标序列
        for(int i=n;i;i--)
        {
            r+=a[i]-b[i];//多出来的+1操作
            if(r<0){f=true;break;}
        }
        if(f)cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
}