CF1856B Good Arrays

题意简述：

给定一个序列 \(a\)，我们定义一个序列 \(b\) 是好的当且仅当对于 \(1\dots n\) 内的每一个 \(i\)，\(a_i\neq b_i\) 且 \(\sum_{i=1}^na_i=\sum_{i=1}^nb_i\)(\(a_i\)，\(b_i\) 均为正整数)。

现在有 \(T\) 组数据，每组数据给定 \(n\) 和序列 \(a\)，判断是否存在一个合法的序列 \(b\)。若存在输出 YES，否则输出 NO。

solution

我们考虑让每一个 \(a_i\) 加上或减去一个数，并且总和不变。

定义 \(sum\) 为当前的变化总量。

可以贪心考虑：让每一个 \(b_i\) 都为 \(1\)，并且让 sum+=a[i]-1，而 \(a_i=1\) 的情况 \(b_i\) 就变为 \(2\)，并让 sum--，这样可以保证当前的变化量最大，可供后面数的选择就多。

若最后 \(sum<0\)，由于每一步取的都是最大变化量，则说明无解

若 \(sum\ge 0\)，若存在 \(b_i=2\)，可以将 \(sum\) 加到这个 \(b_i\) 上；若不存在，则 \(sum=\sum_{i=1}^na_i-1\)，令 \(b_n\) 加上 \(sum\)，一定 \(>a_i\)。当然了 \(n=1\) 的情况一定无解，需要特判掉。

code

#include<cmath>
#include<cstring>
#include<string>
#include<utility>
#include<vector>
#include<queue>
#include<bitset>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
inline int read();
typedef long long ll;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
int n,m,k;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		ll sum=0;
		FOR(i,1,n){
			scanf("%d",&k);
			if(k==1) sum--;
			else sum+=k-1;
		}
		if(sum<0||n==1) puts("NO");
		else puts("YES");
	}
	return 0;
}


inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}

另：电脑没网，手机写的，大家点个赞支持一下qwq