题解：P12702 [KOI 2022 Round 2] 食事计划

Mirasycle · 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;
}