专栏文章

题解：P12948 [GCJ Farewell Round #1] Rainbow Sort

bbh2013
P12948题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mioq3tnw
此快照首次捕获于
2025/12/02 23:18
3 个月前
此快照最后确认于
2025/12/02 23:18
3 个月前
查看原文
题目传送门

1. 题意：

题面已经很清楚了，就不过多赘述了（我这只蒟蒻太懒了），若还有不懂的请看其他大佬的题意。

2. 解法：

经过一段时间的分析，可以发现这道题实际上是让我们判断所有相同颜色卡片是否全都放在一起，若有两张相同数字的卡片的中间有不同数字（对于这两张卡片来说）的卡片那么这组数据一定是不满足规则的，我们可以证明一下：
假设有一张颜色为 ii 的卡片位置为 pos1pos_1， 又有一张颜色为 ii 的卡片，它的位置是 pos2pos_2，这两张卡片的中间有一张颜色为 jj 的卡片，若前两张卡片上写一个数字为 num1num_1，而这张颜色为 jj 的卡片上写一个数字为 num2num_2，根据题目要求 num1≤num2≤num1num_1 \le num_2 \le num_1，说明 num1num_1 即大于等于 num2num_2，且小于等于 num2num_2，根据题目，又有 num1≠num2num_1 \ne num_2，所以 num1num_1 即大于 num2num_2，又小于 num2num_2，不可能。
因此我们判断所有相同颜色卡片是否全都放在一起即可，若成立，则去重后按原数组的顺序输出即可。

3. Ac Code：

CPP
#include <bits/stdc++.h>
using namespace std;

int n, s[100005];
bool isIn[100005];

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t ++) {
		bool f = 1;
		memset(isIn, 0, sizeof(isIn));
		cin >> n;
		for (int i = 1; i <= n; i ++) {
			cin >> s[i];
			if (!isIn[s[i]]) isIn[s[i]] = 1;
			else if (s[i - 1] != s[i]) f = 0;
		}
		cout << "Case #" << t << ": ";
		if (!f) cout << "IMPOSSIBLE" << endl;
		else {
			for (int i= 1; i <= n; i ++)
				if (s[i] != s[i - 1]) cout << s[i] << " ";
			cout << endl;
		}
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...