高仿奢侈手表网站,口碑好的网站设计制作价格,整合营销的概念,企业网站建设方案包含题目描述#xff1a;
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力#xff0c;其中第 i 块是 HiWi的方格组成的长方形。
为了公平起见#xff0c;小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出…题目描述
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力其中第 i 块是 Hi×Wi的方格组成的长方形。
为了公平起见小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足
形状是正方形边长是整数大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤1e5, 1≤Hi,Wi≤1e5
输入样例
2 10
6 5
5 6输出样例
2
分析步骤 第一理清思路 我们拿到这个题目我们先考虑怎么满足第一个条件怎么保证他是正方形呢正方形得保证相邻的两条边一定得是相等的我们可以拿长和宽去除以一个数得到的数相乘就代表着这是我们最多可以求出的正方形数。例如一个长和宽分别是10和20的纸板我们要求出它最多可以有多少个2x2的纸板。只需要拿(长去除以2的商)乘上(宽去除以2的商)--5x1050个。这就是我们推出的数学公式这是本题的第一个特点。 题目中要我们求的是最值那么就代表着我们可以找到一个点在这个点的左边是符合条件的在这个点的右边不符合条件这就是最值的特点。我们还可以发现这个序列一定是递增的从小到大看看那个值是符合条件的。所以即是单调又是最值那么就符合我们的二分的算法条件我们就使用二分算法这是本题的第二个特点。 第二书写主函数构建整体框架 我们可以用pair和这个结构将长和宽放到一个点的位置上。 我们定义左边界为1右边界为1e5。我们的左右边界一定是极端情况的答案只有把极端情况也包含进来了的话那么才不会漏掉答案。l为1是因为长和宽最小是1所以当真的为1时而且只有一个人的时候我们就只能输出1个1x1的巧克力了r为1e5是因为长和宽最大是1e5所以当真的为1e5时且只有一个人的时候最大就是1e5。这就是两个极端情况。 进入我们的while循环只要lr的话就一直循环。求出我们的mid假设mid这个长度的巧克力符合题目中的两个条件的话那么就代表着比mid更小长度的巧克力一定更符合条件因为长度更小意味着数量更多一定可以满足人数的要求和正方形的要求。mid可能是符合条件的最大值再大一点就会错所以直接将mid赋予l区间缩小一点。 设mid这个长度的巧克力不符合题目中的两个条件的话那么就代表着比mid更大长度的巧克力一定更不符合条件因为长度更大意味着数量更少一定可以更不满足人数的要求和正方形的要求。所以就将mid - 1赋予r因为我们检查过了mid不行所以要将mid-1区间缩小一点。 最终退出循环就代表着我们将所有的可能都过了一遍直接输出r。
int main()
{cinnm;for(int i 0 ; i n ; i ){cinq[i].xq[i].y;}int l 1 , r 1e5;while(lr){int mid (l r 1 )/2;if(check(mid)) l mid ;else r mid - 1;}coutrendl;return 0;
}第三书写check函数 定义res等于0让他去记录我们可以产生多少个正方型的巧克力。 我们用for循环去遍历每一个长和宽运用我们推导出的公式再将其加在一起如果数量可以超过m的话就代表这个mid的长度是符合条件的就返回true。否则如果整个for循环结束数量都没有m的话就代表这个mid长度不可以就返回false。
bool check(int mid){LL res 0;for(int i 0 ; i n ; i){res (LL)(q[i].x/mid)*(q[i].y/mid);if(res m) return true;}return false;
}
代码
#include iostream
#include cstring
#include algorithm
#define x first
#define y secondusing namespace std;
typedef long long LL;
typedef pairint, int PII;
const int N 1e510;
PII q[N];
int n , m ;bool check(int mid){LL res 0;for(int i 0 ; i n ; i){res (LL)(q[i].x/mid)*(q[i].y/mid);if(res m) return true;}return false;
}int main()
{cinnm;for(int i 0 ; i n ; i ){cinq[i].xq[i].y;}int l 1 , r 1e5;while(lr){int mid (l r 1 )/2;if(check(mid)) l mid ;else r mid - 1;}coutrendl;return 0;
}
