划分巧克力

分巧克力问题描述儿童节那天有 KK位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 NN块巧克力其中第 ii块是 Hi×WiH**i×W**i的方格组成的长方形。为了公平起见小明需要从这 NN块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足形状是正方形边长是整数;大小相同;例如一块 6×56×5 的巧克力可以切出 66 块 2×22×2 的巧克力或者 22 块 3×33×3 的巧克力。当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么输入描述第一行包含两个整数 N,KN,K(1≤N,K≤1051≤N,K≤105)。以下 N 行每行包含两个整数 Hi,WiH**i,W**i(1≤Hi,Wi≤1051≤H**i,W**i≤105)。输入保证每位小朋友至少能获得一块 1x1 的巧克力。输出描述输出切出的正方形巧克力最大可能的边长。思路分析题目种说我门要对这些巧克力进行划分成一个个的小正方形分配给这K个小朋友而且这些小正方形的边长要求最大那么我们可以先读取每个巧克力的边长然后对他们短的哪一个边进行排序为什么是短的哪一个边因为长的那个边是没有办法切出来那样的正方形的。然后选出短的那一条边里面的最大值作为我们暴力枚举的上限。又因为我们是要求最大值所以我们枚举的时候就从上限开始逐渐向下减#includeiostreamusingnamespacestd;constintN100010;intarr[N][2];intmain(){// 请在此输入您的代码intn,k;cinnk;for(inti0;in;i){cinarr[i][0]arr[i][1];if(arr[i][0]arr[i][1]){intaarr[i][0];arr[i][0]arr[i][1];arr[i][1]a;}}intmax_larr[0][0];longlongsum0;intbc0;for(inti0;in;i){if(max_larr[i][0]){max_larr[i][0];}}for(intimax_l;i1;i--){sum0;for(intj0;jn;j){intb(arr[j][0]/i)*(arr[j][1]/i);sumb;if(sumk){bci;break;}}if(sumk){break;}}coutbc;return0;}这样虽然我们也能通过但是他的时间复杂度还是有点高我们可以使用二分发来写这道题目下面是使用二分法写这道题的代码。#includeiostreamusingnamespacestd;constintN100010;intarr[N][2];intn,k;boolcheck(intmid){longlongtotal0;for(inti0;in;i){intharr[i][0],warr[i][1];total1LL*(h/mid)*(w/mid);if(totalk)returntrue;}returntotalk;}intmain(){cinnk;intr0;for(inti0;in;i){cinarr[i][0]arr[i][1];if(arr[i][0]r)rarr[i][0];if(arr[i][1]r)rarr[i][1];}intl1,ans0;while(lr){intmid(lr)/2;if(check(mid)){ansmid;lmid1;}else{rmid-1;}}coutans;return0;}