AcWing寒假每日一题——Day7分巧克力

1127分巧克力

一、问题描述

儿童节那天有   K \ K  K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有   N \ N  N 块巧克力，其中第   i \ i  i 块是   H i × W i \ H_i×W_i  Hi​×Wi​ 的方格组成的长方形。为了公平起见，小明需要从这   N \ N  N 块巧克力中切出   K \ K  K 块巧克力分给小朋友们。切出的巧克力需要满足：
1、形状是正方形，边长是整数
2、大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数   N \ N  N 和   K \ K  K。

以下   N \ N  N 行每行包含两个整数   H i \ H_i  Hi​ 和   W i \ W_i  Wi​。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤   N , K \ N,K  N,K≤ 1 0 5 10^5 105,
1≤   H i , W i \ H_i,W_i  Hi​,Wi​≤ 1 0 5 10^5 105
输入样例：

2 10
6 5
5 6

输出样例：

2

二、问题分析

  本题与昨天的每日一题思路基本一致，但是是整数的二分法，需注意”mid“是否需要 +1的问题，这点取决于你的写法，当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid或者 l = mid + 1，计算 mid 时不需要加 1。当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid;，此时为了防止死循环，计算 mid 时需要加 1。

代码如下（示例）：

#include<iostream>
#include<algorithm>
using namespace std;
int N,K;
int c[100010],k[100010];
bool check(int mid)
{
    long long res=0;
    for(int i=0;i<N;i++)
    {
        res+=(long long)(c[i]/mid*(k[i]/mid));//可切出块数巧克力的计算公式
        if (res >= K) return true;//总和大于题目中小朋友个数即满足条件返回true
    }
    return false;
}
int main()
{
    scanf("%d%d", &N, &K);
    for(int i=0;i<N;i++)scanf("%d %d",&c[i],&k[i]);//存储每块巧克力的长和宽
    int l=1,r=1e5;//因为每位小朋友至少能获得一块1×1的巧克力，所以左边界定为1，右边界为边长最大值
    while(l < r)
    {
        int mid=(l+r+1)/2;//这里需要将mid+1防止死循环
        if(check(mid))l=mid;//如果mid满足条件，说明在mid的右边还可能有最优值，则令左边界l=mid
        else r=mid-1;//同理
    }
    printf("%d\n", r);//r或l都可
    return 0;
}