描述

给定一个包含N个整数的数组A。你的任务是将A重新排列，使得任意两个相等的整数在数组中都不相邻。

如果存在多个重排后的数组满足条件，输出字典序最小的数组。

这里字典序最小指：首先尽量使第一个整数最小，其次使第二个整数最小，以此类推。

输入

第一行包含一个整数N，表示数组的长度。(1 <= N <= 100000)

第二行包含N个整数，依次是 A1, A2, … AN。(1 <= Ai <= 1000000000)

输出

输出字典序最小的重排数组。如果这样的数组不存在，输出-1。

样例输入

4
2 1 3 3

样例输出

1 3 2 3

思路

本题是《分隔相同字符》的加强版。

《分隔相同字符》的题目分析可以看这里。

在《分隔相同字符》中，数组中的每个元素只能是小写字母(‘a’-‘z’)。换句话说，值域范围是[1, 26]。

而在本题中，数组中的整数值域是[1, 1000000000]，照搬《分隔相同字符》的做法会超时。

不过《分隔相同字符》中介绍的结论还是成立的：无解的充要条件是某个数字出现次数超过(N+1)/2。

所以贪心算法仍然适用：

1) 预处理A1~AN，生成二元组集合S={(a1, c1), (a2, c2), … (am, cm)}。表示a1有c1个，a2有c2个……，am有cm个。

2) 找出c值最大的二元组(ai, ci)。如果ci过多，即ci+ci-1 > n，则无解。

3) 依次找出重排后的第一个数、第二个数……第N个数：

3.1) 找出c值最大的二元组(ai, ci)，如果ci恰好满足：ci+ci-1==n。那么当前数字只能选择ai。

3.2) 如果ci+ci-1 < n，找出a值最小的二元组(aj, cj)。如果前一个数字选的不是aj，那么选择aj。

3.3) 如果前一个数字选的就是aj，再找出a值次小的二元组(ak, ck)。选择ak。

不论上述哪种情况，假设最后选择的是(at, ct)，都要ct–。特别的如果ct=0，则要将(at, ct)从S中删除。

所以我们需要设计一种数据结构，对于二元组集合S={(a1, c1), (a2, c2), … (am, cm)}，支持以下操作(时间复杂度要低)：

1) 找到c值最大的二元组

2) 找到a值最大的二元组

3) 找多a值次大的二元组

4) 对一个二元组(at, ct)进行ct–的操作

5) 删除一个二元组(at, ct)

能支持以上操作的数据结构很多，比如堆、平衡树，上面的操作都能实现O(logN)的复杂度。考虑到C++ STL里的set/map(Java中的TreeSet/TreeMap)内部实现就是平衡树，我们介绍一种利用set/map实现以上操作的方法，非常简单。

可以参考doubleh同学的代码

Tips: 由于set不能修改容器中的元素，所以ct–操作是先删除(at, ct)再添加(at, ct-1)来实现的。

1
2
3
4
5
printf("%d%c", x, " \n"[i == n]);

这句真厉害，受益良多

哈哈 解决了输出空格空行这一历史性难题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    for(int i = 0; i < 5; i++) {
        //前面是string类型，后面中括号下标为0或1，前面都是0，最后一个是1，解决了输出空格空行这一历史性难题。
        printf("%d%c", i, " \t"[i == 4]); 
    }
    cout << "hejian" << endl;
    for(int i = 0; i < 5; i++) {
        printf("%d%c", i, ' ');
        //printf("%d%c", i, " ");  会报错，恍然大悟！！！
    }
    cout << "\thejian" << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

int main()
{
    //题解真聪明，寻找c用set(倒序存储)，寻找a用map
    map<int, int> cnt;
    set<pair<int, int> > S;
    int N, A; cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> A;
        cnt[A]++;
    }
    for(pair<int, int> it : cnt) {
        S.insert(make_pair(it.second, it.first));
    }

    if((--S.end())->first > (N + 1) / 2) {
        cout << -1 << endl;
        return 0;
    }
    int pre = -213;
    for(int i = 0; i < N; i++) {
        int x;
        if((--S.end())->first * 2 - 1 == N - i) {
            x = (--S.end())->second;
        }
        else {
            for(pair<int, int> it : cnt) {
                if(it.first != pre) {
                    x = it.first;
                    break;
                }
            }
        }
        cout << x << ' ';
        pre = x;
        if(--cnt[x] > 0) {
            S.erase(make_pair(cnt[x] + 1, x));
            S.insert(make_pair(cnt[x], x));
        }
        else {
            S.erase(make_pair(cnt[x] + 1, x));
            cnt.erase(x);
        }
    }
    return 0;
}