牛客每日一题 华华给月月准备礼物 二分
华华给月月准备礼物
https://ac.nowcoder.com/acm/problem/23049
链接：https://ac.nowcoder.com/acm/problem/23049
来源：牛客网
来源：牛客网
华华给月月准备礼物
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
输入描述:
第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N个正整数LiL_iLi表示每根木棍的初始长度。 输出描述:
输出一行一个非负整数表示每根木棍的最大长度。
示例1
备注:
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
思路：
二分模板题哦。
假设当前符合要求，那么将 长度扩大 ，绝对会使得答案减小（从而检测是否还满足要求）
假设当前不符合要求，那么将长度减小，绝对会使得答案增大（从而检测可不可以满足要求）
所以这个函数 具有单调性
二分一下 记录 合法答案即可
找不到 ans = 0 （亲测为0）
Code:
/*** keep hungry and calm CoolGuang!***/
//#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=4e18;
const int maxn=5e5+6;
const int mod=20020421;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
bool judge(ll x){
ll ans=0;
for(int i=1;i<=n;i++) ans+=num[i]/x;
return ans>=m;
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;i++) read(num[i]);
ll l=1,r=1e15+7;
ll ans=0;
while(l<=r){
ll mid=(l+r)/2;
if(judge(mid)){
l=mid+1;
ans=mid;
}
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
投递华为等公司10个岗位 >