华华给月月准备礼物
华华给月月准备礼物
https://ac.nowcoder.com/acm/problem/23049
题意：
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为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);
}
查看13道真题和解析
