moiezen

这题是个随机化+二分裸题……………………考场上居然没有想出来……想的出来就怪了吧

我们随机一下增加x的顺序，然后进行二分之前，看看这个x加完之后能不能更新答案，不能就不二分了。具题解所说，这个复杂度是\(logp\)的。

第一次见这种东西，比较蛇皮。

代码如下：

#include <ctime>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=10005,inf=2e9;

int n,p,k,ans;

int a[maxn],b[maxn],fake[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

bool check(int limit) {

	int cnt=0,tmp=0;

	for(int i=1;i<=n;i++) {

		if(tmp+b[i]<=limit)tmp+=b[i];

		else tmp=b[i],cnt++;

	}

	return cnt<k;

}

int solve(int v) {

	int l=0,r=ans;

	for(int i=1;i<=n;i++)

		b[i]=(a[i]+v)%p,l=max(l,b[i]);

	if(!check(ans-1))return ans;

	while(l<r) {

		int mid=(l+r)>>1;

		if(check(mid))r=mid;

		else l=mid+1;

	}

	return r;

}

int main() {

	srand(time(0));

	n=read(),p=read(),k=read();

	for(int i=1;i<=n;i++)

		a[i]=read(),ans+=a[i];

	for(int i=0;i<p;i++)fake[i]=i;

	random_shuffle(fake,fake+p);

	for(int i=0;i<p;i++)

		ans=min(ans,solve(fake[i]));

	printf("%d\n",ans);

	return 0;

}

巴特西

moiezen

最新文章

热门文章