题解 | #L1-6分鸽子#

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const long long maxn=1e5+5;
long long val[maxn];
long long n,m;

int check(long long mid)
{
    long long tmp = 0;
    for(int i=0;i<n;i++) 
    {    
        tmp += val[i]/mid;
    }//判断条件：第i只鸽子可以分出val[i]/x份肉，所用鸽子可以分出tmp份，必须满足tmp>=m
    if(tmp>=m) return 1;
    return 0;
}

int main()
{
    long long left=1,right=0,ans=0,sum=0,mid=0;
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
        cin >> val[i];
        sum = sum+val[i];
    }//输入每只鸽子的重量，以及重量和
    right = sum/m;//对每人所分最多重量mid进行二分查找，易证上界为sum/m
    while(left<=right)
    {
        mid = left+(right-left)/2;
        if(check(mid))
        {
            ans = mid;
            left = mid+1;
        }//如果满足条件，则取数轴右半轴继续二分，找到更好的解
        else right = mid-1;
    }//左右与臂mid相等时，即可退出循环得到ans
    cout << ans <<endl;
    system("pause");
    return 0;
}