华华给月月准备礼物
时间限制：1秒 空间限制：32M
知识点：思维题
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
输入描述：
第一行两个正整数N 、 K N、KN、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N NN个正整数L i L_iLi表示每根木棍的初始长度。
输出描述：
输出一行一个非负整数，表示华华最终得到的n nn根木棍的每根最大长度。
示例1
输入：
5 10 4 4 4 5 3输出：
1说明：
如果长度为2 22，只能得到2 + 2 + 2 + 2 + 1 = 9 2+2+2+2+1=92+2+2+2+1=9根，不够；长度为1 11可以得到4 + 4 + 4 + 5 + 3 = 20 4+4+4+5+3=204+4+4+5+3=20根，足够。所以答案最大是1 11。
示例2
输入：
5 3 1 2 3 4 5输出：
3备注：
1 ≤ N ≤ 2 × 10 5 ， 1 ≤ L i ≤ 10 9 ， 1 ≤ K ≤ 10 9 1≤N≤2×10^5，1≤L_i≤10^9，1≤K≤10^91≤N≤2×105，1≤Li≤109，1≤K≤109
解题思路
首先计算所有木棍的总长度，若总长度小于K KK则直接输出0 00（无法剪出K KK根木棍，最长长度为0 00）；否则采用二分查找确定最大可行长度，左边界l = 1 l=1l=1、右边界r rr为单根木棍的最大长度，每次取m i d = ( l + r + 1 ) / 2 mid=(l+r+1)/2mid=(l+r+1)/2（向上取中避免死循环），通过c h e c k checkcheck函数统计所有木棍按m i d midmid长度裁剪能得到的总根数（每根木棍可裁剪数为l e n [ i ] / m i d len[i]/midlen[i]/mid），若总数≥ K ≥K≥K说明m i d midmid可行，将左边界更新为m i d midmid，否则更新右边界为m i d − 1 mid-1mid−1；最终左边界l即为能剪出K KK根木棍的最大整数长度。该方法通过二分将时间复杂度降至O ( N l o g ( m a x L ) ) O(N log(maxL))O(Nlog(maxL))，适配N NN达2 e 5 2e52e5、L i L_iLi和K KK达1 e 9 1e91e9的规模，高效且精准找到符合要求的最长长度。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e5+10;ll len[N];ll n,k;boolcheck(ll x){ll cnt=0;for(ll i=0;i<n;i++){cnt+=len[i]/x;if(cnt>=k)return1;}return0;}intmain(){cin>>n>>k;ll sum=0,mx=0;for(ll i=0;i<n;i++){cin>>len[i];sum+=len[i];mx=max(mx,len[i]);}if(sum<k){cout<<0;return0;}ll l=1,r=mx;while(l<r){ll mid=(l+r+1)/2;// 向上取中if(check(mid))l=mid;elser=mid-1;}cout<<l<<endl;return0;}
