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

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

首先输入时将

a_i

变为

(a_i+1)

模

s

，显然取模对答案不影响。则题意转化为给

n

个位置填上数，使前缀和模

s

等于

s-1

的位置尽量少，并且遇到这样的位置后前缀和清零。

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

附上代码：

CPP

//#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;
}

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

文章操作

相关推荐

评论

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