CF1807G2 Subsequence Addition (Hard Version) 题解

Larryyu · 2023-03-24 22:34:53 · 题解

Description

数列 a 最开始只有一个数 1，你可以进行若干次操作，每次操作你可以选取 k 个数（k 无限制，小于等于 a 的大小即可），将这 k 个数的和放入 a 的任意一个位置。

给定一个长度为 n 的序列 c，问 a 能否在进行若干次操作后转为 c。

有 t 组数据。

Solution

若当前进行了一次操作，则新加入的数大于当前最小的数（k=1），小于当前所有数的总和（k=n），所以我们对目标数列从小到大排序，若当前的数小于前面所有数的总和，说明这个数是可以实现的否则就不可能实现。

注意：目标序列至少要有一个 1。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int a[5050];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
    int n=read();
    ll sum=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    sort(a+1,a+1+n);
    if(a[1]!=1){ //如果最小的不是1，说明该序列没有1（不可能有非正数）
        cout<<"NO"<<endl;
        return;
    }
    sum=1;
    for(int i=2;i<=n;i++){
        if(a[i]>sum){ //如果大于前缀和，则不可能实现
            cout<<"NO"<<endl;
            return ;
        }
        sum+=a[i];
    }
    cout<<"YES"<<endl;
}
int main(){
    t=read();
    while(t--){
        solve();
    }
    return 0;
}