第一眼:二分!n这么小是方便跑check的吧
冷静后:我单调性呢
于是考虑暴力
发现n很小,check会比较快
注意到如果i不合法,则i的倍数均不合法,考虑使用埃氏筛优化然而还是TLE30pts
正解是个整除分块:
原式等价于求最大的d满足
变形得
\[\sum\lceil\frac{a_i}{d}\rceil \leqslant \lfloor \frac{k+\sum a_i}{d} \rfloor \]注意不到右边可以扯上整除分块
而d越大,左式越小,所以使右式值不变的d中最大的一定更优
那这里r只有\(2\sqrt{k+\sum a_i}\)个,枚举即可
同时还可以注意到从右向左枚举,可以在找到第一个合法d的时候跳出,那考虑从右向左跑整除分块
令\(r\)为右端点, \(n=k+\sum a_i\)
那上一个右端点
\[r_2 = \lfloor \frac{n}{\lfloor \frac{n}{r} \rfloor+1} \rfloor \]就可以枚举了
p.s. 以后别开float,本来常数就小不了多少,再爆float了就得不偿失了对我这题爆float了
float上限\(1.571081981×10^{20}\)
大约是int长度(字面意)的二倍
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 110
#define ll long long
#define ld long double
#define usd unsigned
#define ull unsigned long long
//#define int long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
char buf[1<<21], *p1=buf, *p2=buf;
inline ll read() {
ll ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
ll n, k;
ll a[N], sum, ans, maxn;
bool check(ll d) {
//cout<<"check "<<d<<endl;
ll c=(sum+k)/d, t=0;
for (int i=1; i<=n; ++i) {t+=ceil(double(a[i])/d); if (t>c) return 0;}
//cout<<t<<' '<<c<<endl;
return 1;
}
signed main()
{
#ifdef DEBUG
freopen("1.in", "r", stdin);
#endif
ll c;
n=read(); k=read();
for (int i=1; i<=n; ++i) a[i]=read(), sum+=a[i], maxn=max(maxn, a[i]);
c=sum+k; maxn+=k;
#if 0
for (ll l=1,r; l<=maxn; l=r+1) {
r=c/(c/l);
check(r);
}
#else
for (ll r=maxn,l; r; r=l-1) {
//cout<<l<<' '<<r<<endl;
l=c/((c/r)+1)+1;
if (check(r)) {printf("%lld\n", r); return 0;}
}
#endif
printf("%lld\n", ans);
return 0;
}