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

· · 题解

简单题。

首先有一个显然的贪心策略，每次找到最小的没有被遍历过的店铺，并且这个店铺的类型与上一个遍历的类型不一致。但是会发现对于类似 1 2 3 3 3 这样的数据，后面剩下的店铺全部都是一种类型的，无法与前面不同。

那么考虑如何处理这种情况。发现我们只关心现在还没有遍历过的店铺中类型最多的那一种（假设为 a）。如果这种类型的店铺的剩余次数 x 已经比其余类型的店铺（称之为 b）的剩余次数大 1 时，我们必须要采取交叉遍历的方式，即 a b a b a 的形式遍历，在这里分别对 a，b 类店铺从小到大选取即可。

那么若没有到达这种情况，我们依然按照初始的贪心策略执行即可。

具体的，在代码实现中我们将每种类型店铺中的还没遍历过的最小的店铺放入 priority_queue 中，然后选取最小的，注意特判与前面类型相同。同时用另一个堆维护所有类型出现次数的最大值，每次遍历一个店铺后更新这两个堆即可。当出现特殊情况时进行特殊处理即可。时间复杂度是 O(n\log n) 的。

::::info[Code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf (int)1e18+10
#else
#define inf (int)1e9+10
#endif
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=3e5+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

int a[Max],num[Max],st[Max];
vector<int>v[Max];int ans[Max];
priority_queue<pii,vector<pii>,greater<pii> >q;
priority_queue<pii,vector<pii>,less<pii> >b;

void Out(int n){
    for(int i=1;i<=n;++i)cout << ans[i] << ' ';
    cout << '\n';
}

bool Med;
signed main(){
    int n=read();for(int i=1;i<=n;++i)num[a[i]=read()]++,v[a[i]].pb(i);
    for(int i=1;i<=n;++i){if(num[i])b.push(mk(num[i],i)),q.push(mk(v[i][st[i]],i));}
    int tot=0,has=n;
    while(!q.empty()){
        while(!b.empty()&&b.top().fi!=num[b.top().se]){
            auto it=b.top().se;b.pop();
            if(num[it])b.push(mk(num[it],it));
        }
        int Num=b.top().fi,now=b.top().se;
        if(Num>has-Num+1){cout << "-1\n";return 0;}
        if(Num==has-Num+1){
            while(!q.empty())q.pop();
            for(int i=1;i<=n;++i){
                if(i==now)continue;
                for(int j=st[i];j<(int)v[i].size();++j)q.push(mk(v[i][j],0));
            }
            for(int j=st[now];j<(int)v[now].size();++j){
                ans[++tot]=v[now][j];
                if(!q.empty()){ans[++tot]=q.top().fi;q.pop();}
            }
            Out(tot);exit(0);
        }
        int las=a[ans[tot]];
        now=q.top().se;auto tmp=q.top();q.pop();
        auto Now=tmp;
        if(las==now){
            Now=q.top();q.pop();
            q.push(tmp);
        }
        now=Now.fi;--has;
        num[Now.se]--;st[Now.se]++;
        if(num[Now.se]){q.push(mk(v[Now.se][st[Now.se]],Now.se));}
        ans[++tot]=now;
    }
    Out(tot);
    return 0;
}
/*

*/

::::