526互联

Codeforces Round 857 (Div. 2) A - Likes

发布时间 2023-04-07 21:23:12作者: 2huk

Codeforces Round 857 (Div. 2) A - Likes

题意

有 \(n\) 个人给你点赞或取消赞，其中 \(x\) 表示 \(x\) 号人给你点赞， \(-x\) 表示 \(x\) 号人给你取消赞。在 \(n\) 个单位时间中的每一时刻，都会有一个人进行一次操作。请你安排一种顺序，使得你获得的总点赞数最多及最少。输出第 \(i\) 时刻获得的点赞数。

样例

6
4 3 -1 2 1 -2

1 2 3 4 3 2 
1 0 1 0 1 2

STEP 0

对于本题，要使得所有时刻的总点赞数最多/最少，首先关注的就是点赞/取消赞的次数。

我们用 \(x\) 表示点赞的数量，\(y\) 表示取消赞的数量。

scanf("%d", &n);
for(int i=1; i<=n; i++){
	scanf("%d", a+i);
	if(a[i] > 0){
		x++;	// 点赞
	}
	else{
		y++;	// 取消赞
	}
}

STEP 1 最多

观察样例，不难发现要使总点赞数最多，最优的办法就是先所有人都点完赞，再依次取消赞。

我们已经预处理出来了 \(x\) 和 \(y\)，那么前 \(x\) 时刻中第 \(i\) 时刻的点赞数就应该是 \(i\)。还有 \(y\) 个时刻点赞数就应该以此减少，即第 \(x+i\) 时刻的点赞数应为 \(x-i\)。

for(int i=1; i<=x; i++){
	printf("%d ", i);	
}
for(int i=1; i<=y; i++){
	printf("%d ", x-i);
}

STEP 2 最少

再次观察样例，我们会发现一个神奇的规律：若要使总点赞数最少，答案中前几项都是 1 0 。

为什么呢？思考便知，若要使总点赞数最少，最优的方案就应该是一个人先点上赞再立马取消赞，最后再将剩下不能取消的点赞按次输出。

for(int i=1; i<=y; i++){
	printf("1 0 ");
}
for(int i=1; i<=x-y; i++){
	printf("%d ", i);
}

STEP 3

综上所述，完整代码如下：

#include <iostream>

using namespace std;

const int MAX = 10000010;

int t, n, x, y, a[MAX];

int main(){
	scanf("%d", &t);
	
	while(t--){
		x = y = 0;
		
		scanf("%d", &n);
		for(int i=1; i<=n; i++){
			scanf("%d", a+i);
			if(a[i] > 0){	// 统计点赞数 
				x++;
			}
			else{			// 统计取消赞数 
				y++;
			}
		}
		
		// 求解最多点赞数 
		for(int i=1; i<=x; i++){
			printf("%d ", i);		// 先全部点赞 
		}
		for(int i=1; i<=y; i++){
			printf("%d ", x-i);		// 再依次取消赞 
		}
		puts("");
		
		// 求解最少点赞数 
		for(int i=1; i<=y; i++){
			printf("1 0 ");			// 点完赞立马取消 
		}
		for(int i=1; i<=x-y; i++){
			printf("%d ", i);		// 剩下的依次点赞 
		}
		puts("");
	}
	
	return 0;
}