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

zengziqvan · 2024-10-15 10:38:50 · 题解

题目大意

给定一个长为 n 的序列 A，可以对此序列进行以下操作，操作次数无限制：

选择两个位置 i,j 满足 1\le i< j\le n，将 A_i 加 1 并将 A_j 减 1。

问序列 A 能否通过以上操作形成一个单调不降的序列。

### 题目分析发现最后一个数字显然不会被修改，所以可以从后往前考虑。设已经将 $i+1\sim n$ 位置考虑完毕。考虑第 $i$ 个位置。根据贪心，第 $i$ 个位置的数字要尽量大。有两种情况： - $A_i>A_{i+1}

此时显然需要通过操作使得 A_i\le A_{i+1}。

显然操作 A_{i}-A_{i+1} 次 A_i 取最大值。

不妨让 A_{i-1} 成为被增加的数。

A_i<A_{i+1}

此时如果直接确定 A_i，那么前面的数字限制将更加严格，更难以找到可行解。

所以考虑做若干次形如 (i,j),i<j 的操作，让 A_i 尽量大。

肯定是越接近后面的值越好。

所以 A_i 的最优值显然是 \lfloor \frac{\sum _{k=i}^{n} A_k}{n-i+1}\rfloor。

时间复杂度 \operatorname{O}(n)。

const int N=2e5+10;
int t,n,a[N],b[N];
void solve() {
    cin>>n;
    FOR(i,1,n) a[i]=b[i]=read();
    if(n==1) {
        puts("Yes");
        return ;
    }
    LL um=a[n];
    ROF(i,n-1,2) {
        um+=b[i];
        if(a[i+1]<a[i]) {
            int dt=a[i]-a[i+1];
            a[i]-=dt;
            a[i-1]+=dt;
        } else {
            a[i]=um/(n-i+1);
        }
    }
    if(a[1]<=a[2]) {
        puts("Yes");
    }
    else puts("No");
}
main() {
    cin>>t;
    while(t--) solve();
    return 0;
}