华华给月月准备礼物(二分)
华华给月月准备礼物
https://ac.nowcoder.com/acm/problem/23049
题目描述
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
输入描述:
第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N个正整数LiL_iLi表示每根木棍的初始长度。 输出描述:
输出一行一个非负整数表示每根木棍的最大长度。
示例1
输入
5 10 4 4 4 5 3
输出
1
说明
如果长度为2，只能得到2+2+2+2+1=9根，不够；长度为1可以得到4+4+4+5+3=20根，足够。所以答案最大是1。
示例2
输入
5 3 1 2 3 4 5
输出
3
备注:
1≤N≤2×1051\le N\le2\times10^51≤N≤2×105，1≤Li≤1091\le L_i\le10^91≤Li≤109，1≤K≤1091\le K\le10^91≤K≤109
思路
简单地二分枚举一下答案，因为答案具有单调性，每一段的长度越大，分的份数就越少。就是要注意有的地方会爆int需要开long long，还有就是可能需要的份数是不可能完成的，比如只有一根棍子长度是1，我要分成两份，由于长度是非负整数，所以长度是零。这就意味着二分的时候左边界应该从零开始(90%)
代码
//华华给月月准备礼物(二分)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int a[N];
int n , k;
ll check(int num)
{
ll ans = 0;
for(int i = 0 ; i < n ; i++)
ans += a[i] / num;
return ans;
}
int main()
{
scanf("%d %d" , &n , &k);
for(int i = 0 ; i < n ; i++)
scanf("%d" , &a[i]);
int l = 0 , r = 1e9;
while(l < r)
{
int mid = (ll)(l + r + 1) >> 1;
if(check(mid) >= k)
l = mid;
else
r = mid - 1;
}
printf("%d\n" , l);
return 0;
} 牛客算法竞赛入门课第三节习题题解 文章被收录于专栏
入门课第三节习题题解
