ZOJ 4102 浙江省第16届大学生程序设计竞赛 C题 Array in the Pocket

题意

给 $n$n个数，重新排列，要求每一个位置，新序列和原序列不能相同，字典序最小

题解

要求字典序最小，所以肯定是从前向后去填数
对于每一个位置，一次从小到大枚举可以选择的数，如果填之后，后面的依旧有解，那么就确定这个位置要填的数，否则继续枚举
关键在于判断后面是否有解
假设原序列中从当前位置开始到结束的构成 $a$a；还剩下的可选的数为序列 $b$b
例如：
$4,1,3,2$4,1,3,2
确定了第一个位置选 $1$1之后，对应的 $a,b$a,b分别为：
$a=[1,3,2]$a=[1,3,2]（有序）
$b=[4,3,2]$b=[4,3,2]（无序）
要求对b进行排列，使应对a的位置不能相同
什么情况下无解呢？
某一种数字太多了，多到什么程度？
假设 $a$a中数字 $x$x有很多，如何排列 $b$b？
首先要 $b$b中的 $x$x放到 $a$a中非 $x$x的位置，假设放完之后，还有 $x$x没有放完，就一定会出现放在 $a$a中 $x$x的位置上，就会无解
所以发现，但某种数字的个数超过还剩下位置的长度时，一定是无解

用 $map$map从小到大维护可选的数字，用优先队列维护每种数字出现的个数。

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue<int> heap; //默认从大到小

int num[N];

int main(){
    int T;
    sc(T);
    while(T--){
        int n;
        sc(n);
        vector<int> a(n+2),b(n+2);

        map<int,int> mp;
        heap q;
        heap::point_iterator id[N];

        for (int i=0;i<n;i++) sc(a[i]),mp[a[i]]++;
        for (auto i:mp) 
            id[i.fi]=q.push(i.se*2),num[i.fi]=i.se*2;

        if (q.top()>n) puts("Impossible");else{
            int ffg=0;
            for (int i=0;i<n;i++){
                int fg=0;
                for (auto j:mp){
                    int x=j.fi,y=j.se;
                    if (x==a[i]) continue;
                    q.modify(id[x],num[x]-1); 
                    q.modify(id[a[i]],num[a[i]]-1);
                    if (q.top()>n-i-1) {
                        q.modify(id[a[i]],num[a[i]]);
                        q.modify(id[x],num[x]); 
                    }else{
                        if (y>1) mp[x]--;else mp.erase(x);
                        num[a[i]]--;
                        num[x]--;
                        fg=x;break;
                    }
                }
                if (!fg){
                    ffg=1;break;
                }else b[i]=fg;
            }
            if (ffg) puts("Impossible");else{
                printf("%d",b[0]);
                for (int i=1;i<n;i++) printf(" %d",b[i]); printf("\n");
            }
        }
    }
}