【题解】CF1852B Imbalanced Arrays

ricky_lin / 2023-09-05 / 原文

我们假设当前出长度为 $len$，那么我们在序列中一定有一个 $len/0$，因为一定有一个绝对值最大的数，如果这个数是正数在原序列中就是 $len$，是负数在原序列中即为 $0$。

由上文，我们可以得到，一定不能有 $len$ 和 $0$ 同时出现的情况，也一定不能有 $len$ 和 $now$ 都不能出现的情况。

通过这个性质，我们就可以得到下面的解法：

如果序列中有一个值为 $len$ 的数，那么它一定和所有数的和都为正数，我们可以直接将它去掉，然后其它数 $-1$，这样我们就可以得到一个长度为 $len-1$ 的序列。
如果序列中有一个值为 $0$ 的数，那么它一定和所有数的和都为负数，我们可以直接将它去掉，这样我们也可以得到一个长度为 $len-1$ 的序列。
而若序列中既没有 $len$ 也没有 $0$，或 $len$ 和 $0$ 都有，那么一定是无解的

通过这种方法我们就可以判断能否构造出一种解。

而构造解的方法也很简单：

数值：让删的数的绝对值，从大到小即可（$n \to 1$）
符号：如果删的是 $len$，则为正数；如果删的是 $0$，则为负数。

code：

#include<bits/stdc++.h>
using namespace std;
const int NN = 1e5 + 8;
typedef long long ll;
struct Num{
	int val,pos;
	bool operator < (const Num &x){
		return val > x.val;
	}
}a[NN];
int T,n,hf;
int ans[NN];
ll pre[NN];
bool check(){
	int head = 1, tail = n;
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		if(a[tail].val == cnt && (n-i+1) - a[head].val + cnt == 0) return false;
		if(a[tail].val == cnt) {
			ans[a[tail].pos] = - (n-i+1);
			--tail;
		}
		else if((n-i+1) - a[head].val + cnt == 0){
			ans[a[head].pos] = (n-i+1);
			++head,++cnt;
		}
		else return false;
	}
	return true;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i = 1; i <= n; ++i) scanf("%d",&a[i].val),a[i].pos = i;
		sort(a+1,a+1+n);
		hf = -1;
		for(int i = 1; i <= n; ++i) pre[i] = pre[i-1] + a[i].val;
		if(!check()){puts("NO");continue;}
		puts("YES");
		for(int i = 1; i <= n; ++i) printf("%d ",ans[i]);
		puts("");
	}
}