题解：CF2244B Nikita and Books

Calamity_Link · 2026-08-09 11:23:34 · 题解

Upd

2026.8.9 初稿。

思路

本题最优时间复杂度 O(tn)。

考虑贪心。

注意到对于每堆书，其后面的书的总和要尽可能多，因此只需判断序列 a 能否通过若干次操作转化为 [1,2,3,\cdots,n-2,n-1,s-\frac{n(n-1)}{2}]，其中 s 是书的总数。

AC Code

#include<bits/stdc++.h>
using namespace std;
long long t,n,a[200001],sum,flag,i;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++)
            cin>>a[i];
        flag=1;
        for(i=1;i<n;i++){
            if(a[i]+a[i+1]<=a[i-1]*2+2){
                flag=0;
                break;
            }
            a[i+1]=a[i]+a[i+1]-a[i-1]-1;
            a[i]=a[i-1]+1;
        }
        if(flag)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}