自动搬运

查看原文

来自洛谷，原作者为

	Mirasycle 遗憾离场

搬运于2025-08-24 23:17:33，当前版本为作者最后更新于2025-06-05 10:34:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

超级简单题。

首先如何判定合法？找到序列众数，只要其出现次数 $\le \lceil\dfrac{n}{2} \rceil$，就必然合法，不需要考虑出现次数次大的数之类的，因为我们只要交替排列就必然是一种合法的方案。

于是推广一下，假设我们已经填入了一段前缀，那么如果长度为 $k$ 的后缀中众数出现次数 $\le \lceil\dfrac{k}{2} \rceil$ 就必然能继续往后面填。

由于本题是字典序，所以我们按位贪心，一位一位填。首先一个决策点是与上一个位置中的 $a$ 不相同的数中位置最小的数，但是我们不能直接填这个，因为填完之后可能会造成后缀不满足上一段的判定要求。

于是我们就先判断一下如果这个数不填众数，后面会不会不合法，使用 std::set 维护剩余数中的众数。每次找到众数如果这个位置不填它的话，后续位置不能满足上述要求就填它，注意如果是多个众数的话需要取位置字典序最小的。否则我们就填位置字典序最小的点。

时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=3e5+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
struct node{
	int c,pos,x;
	bool operator < (const node &rhs) const{ return c>rhs.c||(c==rhs.c&&pos<rhs.pos); }
};
int a[maxn],cnt[maxn],cur[maxn];
int lst[maxn],nxt[maxn],col,n;
set<node> s1; set<pair<int,int> > s2;
set<pair<int,int> >::iterator it;
void op(int x){
	cout<<cur[x]<<" "; col=x;
	s1.erase((node){cnt[x],cur[x],x}); s2.erase(mp(cur[x],x));
	cnt[x]--; if(!cnt[x]) return ;
	cur[x]=nxt[cur[x]]; s1.insert((node){cnt[x],cur[x],x}); s2.insert(mp(cur[x],x));
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]; cnt[a[i]]++;
		if(lst[a[i]]) nxt[lst[a[i]]]=i;
		else cur[a[i]]=i;
		lst[a[i]]=i; 
	}
	for(int i=1;i<=n;i++)
		if(cnt[i]) s1.insert((node){cnt[i],cur[i],i});
	for(int i=1;i<=n;i++)
		if(cur[i]) s2.insert(mp(cur[i],i));
	if((*s1.begin()).c>(n+1)/2){ cout<<"-1"; return 0; }
	for(int i=1;i<=n;i++){
		node z=*s1.begin();
		if(z.c>(n-i+1)/2) op(z.x);
		else{
			it=s2.begin();
			if((*it).se!=col) op((*it).se);
			else{ ++it; op((*it).se); }
		}
	}
	return 0;
}