时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个包含N个整数的数组A。你的任务是将A重新排列，使得任意两个相等的整数在数组中都不相邻。
如果存在多个重排后的数组满足条件，输出字典序最小的数组。
这里字典序最小指：首先尽量使第一个整数最小，其次使第二个整数最小，以此类推。
输入
第一行包含一个整数N，表示数组的长度。(1 <= N <= 100000)
第二行包含N个整数，依次是 A1, A2, ... AN。(1 <= Ai <= 1000000000)
输出
输出字典序最小的重排数组。如果这样的数组不存在，输出-1。
样例输入
4
2 1 3 3
样例输出
1 3 2 3
这道题不算太水, 但是是个比较裸的数据结构题, 用C++ STL写很方便. 要求维护一个二元组$(x,y)$的集合 $(x, y \in \mathbb{N}^+)$, 支持如下操作:
Implementation
#include <bits/stdc++.h> using namespace std; map<int,int> cnt; typedef pair<int,int> P; set<P, greater<P>> s; int main(){ int n; cin>>n; for(int x, i=0; i<n; cin>>x, cnt[x]++, i++); for(auto &x:cnt) s.insert({x.second, -x.first}); if(s.begin()->first >(n-1)/2+1){puts("-1"); return 0;} for(int res, pre=0; n--; pre=res){ int ma=s.begin()->first; if(ma>(n-1)/2+1){ //caution when n==0 auto it=s.begin(); if(it->second==pre) ++it; res=-it->second; if(it->first==1) cnt.erase(res); else{ s.insert({it->first-1, it->second}); cnt[res]--; } s.erase(it); } else{ auto it=cnt.begin(); if(it->first==pre) ++it; res=it->first; s.erase({it->second, -res}); if(it->second==1) cnt.erase(it); else{ it->second--; s.insert({it->second, -res}); } } cout<<res<<‘ ‘; } cout<<endl; }
原文：http://www.cnblogs.com/Patt/p/5747698.html