codeforces 830C Bamboo Partition

题目链接

codeforces 830C Bamboo Partition

分析

首先我们需要知道什么样的d是满足的.对于任意的 $i$

$$\sum [\frac{a[i]+d-1}{d}] - a[i] \le k$$

因此

$$d \le k+\sum a[i]$$

注意条件项中的 $[\frac{a[i]+d-1}{d}]$ 在这中由于 d 只有 $\sqrt{a[i]}$ 种可能，因此，可以分段枚举d

AC code

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define PI acos(-1)
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define ms(x,v) memset((x),(v),sizeof(x))
using namespace std;
const int MOD = 1e9+7;
const double eps = 1e-8;
typedef long long LL;
typedef long double DB;
typedef pair<int,int> PII;
const int maxn=  1e5+10;

int a[maxn];
LL n,k;
bool ok(LL d){
    LL ret =0;
    for (int i=0 ; i<n ; ++i){
        ret += (a[i]-1+d)/d;
    }
    return ret * d <= k;
}
int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>k;
    for(int i=0 ; i<n ; ++i)cin>>a[i],k+=a[i];
    LL ans =0;
    for(LL i=1 ; i<=sqrt(k)+1 ; ++i){
        if(ok(i))ans = max(ans,i);
        if(ok(k/i)) ans = max(ans,k/i);
    }
    cout << ans<<"\n";

    return 0;
}