题目描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:
1. 形状是正方形,边长是整数
2. 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?
输入格式
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
样例输入
复制
2 10 6 5 5 6
样例输出
复制
2
个人分析
这个博客是我自己用来记录二分算法的模板的 如果我记录的有错误 烦请谅解
这是一个二分的模板
while (l < r)
{
mid = (l + r + 1) / 2;//(如果r=mid-1 那么就需要将mid+1)
if (check(mid) == true)//检查中点是否符合要求
{
l = mid;
}
else
{
r = mid - 1;
}
}
其中一般mid=(l + r)/2
但是因为存在了r = mid-1 那么就需要在(l+r)里面再加上1 否则会出现死循环
首先if (check(mid) == true)是检查中点处是否符合规则
check检查的规则是看巧克力分的总数sum有没有大于小孩子的数量k
如果检查符合规则 那么就是在中点左边的边长一定可以分出足够多的巧克力给小朋友
但是我需要找的是尽可能最大的巧克力 所以需要往右边找 也就是缩左边界l=mid
(这里不让mid+1是因为中点mid是符合规则的 不能把mid给舍弃)
如果程序到达else条件下 说明中点检查不符合规则
那么就需要往左边找 要缩右边界 也就是r=mid-1
(这里要让mid-1是因为mid本身是不符合规则的 所以需要舍弃)
题解代码
//#include<bits/stdc++.h> //vs2022不让用 交题目的时候可以用
#include<iostream>
using namespace std;
long long int n, k;
long long int food[100001][2] = { {0} };
long long int l, r;
bool check(long long int e)
{
long long int sum = 0;
for (long long int i = 1; i <= n; i++)
{
sum = sum + (food[i][0] / e) * (food[i][1] / e);
}
if (sum < k)//分的总数量小于小孩子的数量
{
return false;
}
return true;
}
int main()
{
scanf("%lld %lld", &n, &k);
for (long long int i = 1; i <= n; i++)
{
scanf("%lld %lld", &food[i][0], &food[i][1]);
}
l = 1, r = 100000;
long long int mid;
while (l < r)
{
mid = (l + r + 1) / 2;//(如果r=mid-1 那么就需要将mid+1)
if (check(mid) == true)//检查中点是否符合要求
{
l = mid;
}
else
{
r = mid - 1;
}
}
printf("%lld\n",l);
return 0;
}
标签:巧克力,真题,int,mid,long,check,蓝桥,2017,小朋友
From: https://blog.csdn.net/m0_74242327/article/details/136985717