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

· · 题解

题目传送门

1. 题意：

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

2. 解法：

经过一段时间的分析，可以发现这道题实际上是让我们判断所有相同颜色卡片是否全都放在一起，若有两张相同数字的卡片的中间有不同数字（对于这两张卡片来说）的卡片那么这组数据一定是不满足规则的，我们可以证明一下：

假设有一张颜色为 i 的卡片位置为 pos_1， 又有一张颜色为 i 的卡片，它的位置是 pos_2，这两张卡片的中间有一张颜色为 j 的卡片，若前两张卡片上写一个数字为 num_1，而这张颜色为 j 的卡片上写一个数字为 num_2，根据题目要求 num_1 \le num_2 \le num_1，说明 num_1 即大于等于 num_2，且小于等于 num_2，根据题目，又有 num_1 \ne num_2，所以 num_1 即大于 num_2，又小于 num_2，不可能。

因此我们判断所有相同颜色卡片是否全都放在一起即可，若成立，则去重后按原数组的顺序输出即可。

3. Ac Code：

#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;
}