Codeforces 830C Bamboo Partition 其他

时间：2023-03-09 09:31:25
Codeforces 830C Bamboo Partition 其他

原文链接https://www.cnblogs.com/zhouzhendong/p/CF830C.html

题解

把问题转化成求最大的 $d$ ，满足
$$\sum_{1\leq i \leq n}(\lceil a_i / d\rceil \times d - a_i )\leq k$$
移项
$$(d\sum_{1\leq i \leq n } \lceil a_i / d \rceil )\leq k + \sum_{1\leq i \leq n} a_i$$
于是可能的 $d$ 就只可能有 $O(\sqrt{k+\sum_{1\leq i \leq n} a_i})$ 种。直接暴力枚举并判断就好了。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

LL read(){

	LL x=0,f=1;

	char ch=getchar();

	while (!isdigit(ch)&&ch!='-')

		ch=getchar();

	if (ch=='-')

		f=0,ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?x:-x;

}

const int N=105;

int n;

LL k;

int a[N];

int check(LL x){

	LL tot=0;

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

		tot+=x*((a[i]+x-1)/x);

	return tot<=k;

}

int main(){

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

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

		k+=a[i]=read();

	LL ans=1;

	for (LL i=sqrt(k)+1;i>=1;i--){

		if (check(i))

			ans=max(ans,i);

		if (check(k/i))

			ans=max(ans,k/i);

	}

	cout << ans;

	return 0;

}