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

我们充分发扬人类智慧，注意到这题数据不太好造，数据可能很弱，所以考虑随机化乱搞。

先考虑一种假贪心，从前往后依次取数，如果当前这个数加进去后不会产生空行就把它加进去，否则把他放进一个队列里，然后每次按顺序判断 $a_i$ 前先尝试将队列开头的元素放进去，这样直接交上去只会 Wa 3 个点。

考虑乱搞，将 $a_i$ 升序排序后再进行一次判断，然后就能通过这题了。（？？？）

乱搞代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,a[1000010];
int ans;
int sh[1000010],av[1000010],id,u[1000010];
int qu[1000010],l,r;
void get4(){
	l=1,r=0;
	int sum=1,cnt=0,ui=0;
	for(int i=1;i<=n;i++){
		while(l<=r&&(a[qu[l]]+sum)%k!=0){
			sum=(sum+a[qu[l]])%k;
			u[++ui]=qu[l];
			l++;
		}
		if((sum+a[sh[i]])%k==0)qu[++r]=sh[i];
		else{
			sum=(sum+a[sh[i]])%k;
			u[++ui]=sh[i];
		}
	}
	while(l<=r){
		if(sum%k==0)cnt++,sum++;
		sum=(sum+a[qu[l]])%k;
		u[++ui]=qu[l];
		l++;
	}
	if(cnt<ans){
		for(int i=1;i<=n;i++)av[i]=u[i];
		ans=cnt;
	}
}
bool cmp1(int x,int y){
	return a[x]<a[y];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];a[i]++;
	}
	ans=1e9;
	for(int i=1;i<=n;i++)sh[i]=i;
    get4();
	sort(sh+1,sh+1+n,cmp1);
	get4();
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++)cout<<av[i]<<" ";
	cout<<'\n';
	return 0;
}

但是我们注意到只需要造 $s=10$ 和前一半是 1 和后一半是 8 的数据就能轻松卡掉了。

所以我们再降序排序一次并顺便 shuffle 几十次再判一下就能过了。

加强版乱搞代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,a[1000010];
int ans;
int sh[1000010],av[1000010],id,u[1000010];
int qu[1000010],l,r;
void get4(){
	l=1,r=0;
	int sum=1,cnt=0,ui=0;
	for(int i=1;i<=n;i++){
		while(l<=r&&(a[qu[l]]+sum)%k!=0){
			sum=(sum+a[qu[l]])%k;
			u[++ui]=qu[l];
			l++;
		}
		if((sum+a[sh[i]])%k==0)qu[++r]=sh[i];
		else{
			sum=(sum+a[sh[i]])%k;
			u[++ui]=sh[i];
		}
	}
	while(l<=r){
		if(sum%k==0)cnt++,sum++;
		sum=(sum+a[qu[l]])%k;
		u[++ui]=qu[l];
		l++;
	}
	if(cnt<ans){
		for(int i=1;i<=n;i++)av[i]=u[i];
		ans=cnt;
	}
}
bool cmp1(int x,int y){
	return a[x]<a[y];
}
bool cmp2(int x,int y){
	return a[x]>a[y];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];a[i]++;
	}
	ans=1e9;
	for(int _=1;_<=30;_++){
		for(int i=1;i<=n;i++)sh[i]=i;
		random_shuffle(sh+1,sh+1+n);
		get4();
	}
	sort(sh+1,sh+1+n,cmp1);
	get4();
	sort(sh+1,sh+1+n,cmp2);
	get4();
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++)cout<<av[i]<<" ";
	cout<<'\n';
	return 0;
}

这题蓝？真的假的？

全机房看着 jiangly 的题解肘了一个晚上才肘出来。

我们转化一下题意，我们将每个文章的长度先加上一，及加上标题的长度，然后排列时如果文章第一行碰到一页最后一行，则需换到下一页并产生一个代价，求最少代价，注意到每个文章产生的贡献只和它的长度对 $s$ 取模后的值有关，并且注意到取模完之后是 $0$ 的放在最前面一定不劣，此时可以发现所有同余的数字是等价的，因此我们可以先统计一下每个余数出现了多少次。

首先证明一个结论。

如果序列中不存在绝对众数，那么一定可以构造一个不产生空行的解。

考虑一个调整策略，我们先将出现最多的数字设为主元，先将主元排成一排，每次通过在主元与主元之间的空隙或主元与边界之间的空隙防止非主元元素来实现宏观调控，如图所示。

其中 $CZS$ 表示主元。

其中 $CZR$ 表示多于元素。

我们不妨假设进行宏观调控的 $CZR$ 后面的 $CZS$ 会导致再往后一格会出现空行的情况，由于 $CZR$ 和 $CZS$ 不相等，此时 $CZR$ 的宏观调控可以成功避免出现空行。

而 $CZR$ 的总数大于等于 $CZS$ 的总数，因此 $CZR$ 肯定够用。

那么如果 $CZR$ 太多了怎么办？

当调控的过程当中出现一个新的元素 $nkh$ 成为新的众数时，我们在消耗至这种情况时将主元更改为 $nkh$。

容易发现这样不断的转化，问题就一定会划归为一个更小的等价问题，因此这样的策略一定是可行的。

那如果存在一个绝对众数呢？

可以发现最后要么转变为刚才的情况，要么变成只有主元作为单一元素的情况，如图所示。

为什么这样转换为只有主元单一元素一定更优呢？

首先我们规避掉 $CZR$ 够用，能够构造 0 的情况，因为这样一定是最优的。

那么 $CZR$ 一定不够用，此时不同于刚才的情况必将导致最后剩下一个另一个元素 $CZR$。我的 $CZR$ 都不够用了，我还减少一次宏观调控的机会并且带来一个产生新的空格的风险，可以发现这样一定不优于留下 $CZS$ 的情况，因此直接按照这样的策略贪心即可。

代码实现比较简单，用 set 维护，每次取出最大和次大值，模拟一下即可。

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
inline pair<int,int> mk(int i,int j){return make_pair(i,j);}
set<pair<int,int>>S;
int n,s,now,sum,cur[maxn];
vector<int>ANS,stk[maxn];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>s;
	for(int i=1;i<=n;++i){
		int x;cin>>x;x=(x+1)%s;
		cur[x]=0;stk[x].push_back(i);
	}
	for(int i=0;i<s;++i)
		if(stk[i].size())
			S.insert(mk(-stk[i].size(),i));
	while(S.size()>1){
		auto fir=*S.begin();
		auto sec=*next(S.begin());
		if(now+fir.second==s-1){//选择宏观调控
			S.erase(sec);
			++sec.first;
			now=(now+(sec.second))%s;
			ANS.push_back(stk[sec.second][cur[sec.second]++]);
			if(sec.first!=0)
				S.insert(sec);
		}
		else{//选择消耗CZS
			S.erase(fir);
			++fir.first;
			now=(now+(fir).second)%s;
			ANS.push_back(stk[fir.second][cur[fir.second]++]);
			if(fir.first!=0)
				S.insert(fir);
		}
	}
	if(S.size()){
		auto czs=*S.begin();
		while(czs.first!=0){
			++czs.first;
			if(now==s-1)++sum,now=0;
			ANS.push_back(stk[czs.second][cur[czs.second]++]);
			now=(now+czs.second)%s;
		}
	}
	cout<<sum<<"\n";
	for(auto i:ANS)cout<<i<<" ";
	return 0;
}