题意:
二月中旬虐狗节前夕,华华决定给月月准备一份礼物。为了搭建礼物的底座,华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍,他想将每根都裁剪成若干段自己想要的长度,并丢掉多余的部分。因为华华的手很巧,所以他的裁剪过程不会有任何的失误。也就是说,对于一根长度为N的木棍,华华可以精准的将它们裁剪为若干段木棍,使它们的长度之和为N。
华华不知道裁剪成多长比较好,所以干脆越长越好。不过由于华华有点强迫症,所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢?
题解:
首先假设x为最后答案,那么显然我们能够判断x是否成立(贪心将每个圆木棍 分成长度为x的小木棍看是否>=k),
并且ans有着明显的单调性,所以直接二分就可以了
代码
#pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define yes puts("YES") #define no puts("NO") #define ios ios::sync_with_stdio(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef vector<int> VI; const int maxn = 1e6 + 6; const LL inf = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;} LL inv(LL x){return qp(x,mod-2);} //head int _,n,m,k,a[maxn],b[maxn],c[maxn]; bool ok(int x){ int ans=0; for(int i=1;i<=n;i++){ ans+=a[i]/x; if(ans>=k) return 1; //cout<<x<<','<<ans<<endl; } return 0; } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l=1,r=1e9,ans=0; while(l<=r){ int mid=l+r>>1; if(ok(mid)){ l=mid+1; ans=mid; } else r=mid-1; } printf("%d\n",ans); }