@[TOC]
试题链接
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
二月中旬虐狗节前夕,华华决定给月月准备一份礼物。为了搭建礼物的底座,华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍,他想将每根都裁剪成若干段自己想要的长度,并丢掉多余的部分。因为华华的手很巧,所以他的裁剪过程不会有任何的失误。也就是说,对于一根长度为N的木棍,华华可以精准的将它们裁剪为若干段木棍,使它们的长度之和为N。
华华不知道裁剪成多长比较好,所以干脆越长越好。不过由于华华有点强迫症,所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢?
输入描述:
第一行两个正整数N、K,表示木棍原本的根数和华华希望得到的木棍根数。 第二行N个正整数Li表示每根木棍的初始长度。
输出描述:
输出一行一个非负整数表示每根木棍的最大长度。
示例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
备注:
题解:
二分的模板题吧
我们假设最后结果是ans,那么小于等于ans的答案都是符合条件的(只是不是最大),而大于ans的肯定不行,那ans怎么确定呢?
这里就用到二分,一开始左界left=1,右界right=最长的木棍长度(也可以初始值为1e9+1,因为木棍再长也不可能大于1e9),然后去这段区间的中间值mid,然后判断mid是否符合条件,如果符合条件,说明mid左边的都可以,右边的不一定,右边有可能还有更优的答案,也可以没有,所以left=mid+1,开始探索mid右边的未知区域。但如果不符合条件,说明当前mid右边更不符合,只有左边才存在符合条件,right=mid-1,探索左边区域,一直这样二分找到最佳答案
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+4; ll l[maxn]; int n,k; ll sum; ll check(ll len) { sum=0; for(int i=1;i<=n;i++)sum+=l[i]/len; return sum; } int main() { cin>>n>>k; for(int i=1;i<=n;i++)cin>>l[i]; ll ans=0; ll left=1,right=1e9+1,mid; while(left<=right) { mid=(left+right)>>1; if(check(mid)>=k) { left=mid+1; ans=mid; } else { right=mid-1; } } cout<<ans; return 0; }
推荐例题:
NC16462 跳石头
noip day2 T1题目,也是经典的二分题目,刚学二分的可以练练手