2019浙江省赛C-错排问题,贪心

题目大意:

给你一个序列，让你找出一种字典序最小的错排。

题目思路:

1.将这个问题拓展一下:
给两个序列（不一定全等）。找字典序最小的错排。

2.错排存在的充要条件为：两个序列的和中出现次数最多的数 不超过 序列总长.(鸽巢定理)

3.依靠条件2,我们自然可以直接贪心的从小往大的填数，同时保证任意时刻，条件2成立即可（剩下的数最多出现次数不超过剩下的位置）.

那么填数分两个阶段，第一个阶段贪心的填最小值和次小值。第二阶段到达条件2的临界条件。

代码有注释:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int a[maxn] , b[maxn] , n;
set<int> s;
multiset<int> ms; // 动态维护总出现次数
unordered_map<int,int> Tcnt , cnt; // 总体每个数出现次数和下面一列
void del (int x , int down){
    
    auto g = ms.find(Tcnt[x]);
    ms.erase(g);
    Tcnt[x]--;
    if (Tcnt[x] == 0) Tcnt.erase(x);
    else ms.insert(Tcnt[x]);
    if (down)
        cnt[x]--;
    if (cnt[x] == 0){
    
        s.erase(x);
        cnt.erase(x);
    }
}
int c[maxn];
void imp (int x){
    
    vi mx;
    for (auto & g : Tcnt)
        if (n - x + 1 == g.second) mx.push_back(g.first);
    if (mx.size() == 1){
    
        vi ot;
        for (auto & g : cnt)
            if (g.first != mx[0])
                for (int i = 1 ; i <= g.second ; i++)
                    ot.push_back(g.first);
        sort(ot.begin(),ot.end());
        reverse(ot.begin(),ot.end());
        for (int i = x ; i <= n ; i++){
    
            if (a[i] == mx[0]) {
    
                b[i] = ot.back();
                ot.pop_back();
            }else {
    
                b[i] = mx[0];
            }
        }
    }else {
     // 真 唯一方案
        for (int i = x ; i <= n ; i++){
    
            if (a[i] == mx[0]) b[i] = mx[1];
            else b[i] = mx[0];
        }
    }
    return ;
}
int main()
{
    

    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--){
    
        s.clear();
        ms.clear();
        Tcnt.clear();
        cnt.clear();
        cin >> n;
        for (int i = 1 ; i <= n ; i++){
    
            cin >> a[i];
            s.insert(a[i]);
            cnt[a[i]]++;
            Tcnt[a[i]] += 2;
        }
        // 判断局面合法
        bool ok = true;
        for (auto & g : Tcnt){
    
            if (g.second > n) {
    
                ok = false;
                break;
            }
            ms.insert(g.second);
        }
        if (!ok){
    
            cout << "Impossible" << endl;
            continue;
        }
        /* 放的时候有三种情况: 0.若 上下两行的数的并 最多出现次数 = 剩下位置的个数 ,这种局面直接处理 1.若当前对位不是最小值，就放最小值. 2.否则放次小值 要维护: 1.当前元素最小值，次小值 2.每个数出现次数以及出现次数的最大值 */
        for (int i = 1 ; i <= n ; i++){
    
            int mxcnt = *ms.rbegin();
            if (mxcnt == n - i + 1){
    
                imp(i);
                break;
            }
            int miv[4], d = 0;
            for (auto & g : s){
    
                miv[++d] = g;
                if (d == 2) break;
            }
            if (a[i] != miv[1]) b[i] = miv[1];
            else b[i] = miv[2];
            del(a[i] , false);
            del(b[i] , true);
        }
        for (int i = 1 ; i <= n ; i++){
    
            cout << b[i];
            if (i == n) cout << endl;
            else cout << " ";
        }
    }
    return 0;
}