刷题记录:牛客NC23049华华给月月准备礼物

传送门:牛客

题目描述:

二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
输入:
5 5 
10 
40 
13 
22 
7 
输出:
1

一道简单的二分答案题,脱离复杂的题面来说是一道经典的切木棍的题目,曾经以各种面纱在各大OJ上出现过,下面讲述一下这种题目的具体思路

具体思路:

1. 首先我们可以二分我们的每根木棍的长度(当然此时我们二分出来的木棍长度并不一定满足我们的条件,只是用来二分而已)
2. 然后我们根据我们二分出来的木棍来判断是不是符合条件,此时我们就计算每一根原来的木棍能分成几根我们二分出来的木棍即可,如果数量总和满足我们的需求,就说明我们或许可以取更长的,反之则不可

注意点:此题需要开long long且如果你用的二分习惯和我一样的话注意ans的初始值一定要赋值为0,因为答案可能为0(不然第一个点过不去),但是注意此时我们的l是不能刚开始就赋值为0的,因为这会导致我们的mid在跑二分的时候成为0导致除0错误

具体的代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
ll N,K;
ll a[maxn];
ll check(ll mid) {
	ll sum=0;
	for(int i=1;i<=N;i++) {
		sum+=(a[i]/mid);
	}
	if(sum>=K) return true;
	else return false;
}
int main() {
	N=read();K=read();
	ll l=1,r=-1;
	for(int i=1;i<=N;i++) {
		a[i]=read();
		r=max(r,a[i]);
	}
	ll ans=0;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) {
			ans=mid;
			l=mid+1;
		}else {
			r=mid-1;
		}
	}
	cout<<ans<<endl;
	return 0;
}