题解：P12763 [POI 2018 R2] 诗集 Book of poetry

· · 题解

由于 DP 等其他东西难以考虑顺序，所以考虑贪心。

首先输入时将 a_i 变为 (a_i+1) 模 s，显然取模对答案不影响。则题意转化为给 n 个位置填上数，使前缀和模 s 等于 s-1 的位置尽量少，并且遇到这样的位置后前缀和清零。

考虑从前往后决策当前地方填什么数。注意到由于鸽巢原理，当前决策到某个位置时只要还有两种不同的可用值，我们一定可以做到不增加空行：一个会增加则另一个一定不会。因此我们可以贪心地每次选择现在剩余出现次数最多的数去填，如这个不合法则换用次小值，如无次小值说明一定会出现一个空行，让答案加一。维护当前出现次数最多次多的值使用 set 即可。

附上代码：

//#pragma GCC optimize(2,3)
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mk make_pair
#define fir first
#define sec second
#define pb emplace_back
#define put putchar
using namespace std;
il int rd(){
    int jya=0,tl=1;char jyt=getchar();
    while(!isdigit(jyt)){if(jyt=='-')tl=-1;jyt=getchar();}
    while(isdigit(jyt)){jya=(jya<<1)+(jya<<3)+(jyt-'0');jyt=getchar();}
    return jya*tl;
}
il void wr(int jjy){
    if(jjy<0)putchar('-'),jjy=-jjy;
    if(jjy>9)wr(jjy/10);
    putchar(jjy%10+48);
}
const int JYAAKIOI=1e18,N=1e6+10,M=1e6,mod=998244353;
int n,a[N],s,cnt[N],ans,now,cur[N],nowsz;
set<pii,greater<pii> >st;
vector<int>g[N];
vector<int>anss;
signed main(){
    n=rd();s=rd();
    for(int i=1;i<=n;++i){
        a[i]=(rd()+1)%s;
        ++cnt[a[i]];
        g[a[i]].pb(i);
    }
    for(int i=0;i<=M;++i)if(cnt[i])st.insert(mk(cnt[i],i));
//  cout<<cnt[1]<<endl;
    nowsz=st.size();
    for(int i=1;i<=n;++i){
        int nowcnt=(*st.begin()).fir,nowid=(*st.begin()).sec;
        if((now+nowid)%s!=s-1||nowsz==1){
            anss.pb(g[nowid][cur[nowid]]);
            ++cur[nowid];
            now=(now+nowid)%s;
            if(now==s-1&&i!=n){
                ++ans;
                now=0;
            }
            st.erase(st.begin());
            --nowsz;
            if(nowcnt>1)st.insert(mk(nowcnt-1,nowid)),++nowsz;
        }
        else{
            auto tmp=*st.begin();
            st.erase(st.begin());
            int nowcnt=(*st.begin()).fir,nowid=(*st.begin()).sec;
            anss.pb(g[nowid][cur[nowid]]);
            ++cur[nowid];
            now=(now+nowid)%s;
            st.erase(st.begin());
            --nowsz;
            if(nowcnt>1)st.insert(mk(nowcnt-1,nowid)),++nowsz;
            st.insert(tmp);
        }
    }
    wr(ans),put('\n');
    for(auto v:anss)wr(v),put(' ');
    return 0;
}