reference
站在用戶的角度思考問題，與客戶深入溝通，找到屏山網(wǎng)站設計與屏山網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設計與互聯(lián)網(wǎng)技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都網(wǎng)站設計、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、空間域名、雅安服務器托管、企業(yè)郵箱。業(yè)務覆蓋屏山地區(qū)。
重慶分公司
重慶分公司
#include
#include
using namespace std;
/*使得將巧克力按照邊長maxX進行切分
，切分成的份數(shù)要大于等于K，
而如果按照maxX+1進行切割
，將不再能夠切出K塊。
如果從1-逐個查找，那么肯定超時，所以采用二分查找。
*/
int n,k,a[],b[];//a 4 high ,b 4 wide
bool ok(int x){
int cnt=0;
for (int i = 1; i <= n; i ++ ){
cnt+=(a[i]/x)*(b[i]/x);//可以切割成的邊長合理的正方形巧克力的塊數(shù)
if(cnt>=k){
return true;
}
}
return false;
}
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i]>>b[i];
}
int l = 0,r = ;
while(l<=r){
int m = l/2+r/2;
if(ok(m)){
l=m+1;
}else{
r=m-1;
}
}
cout< 題目描述
兒童節(jié)那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友們。
小明一共有 NN 塊巧克力，其中第 ii 塊是 H_i \times WiH
i
?
×Wi 的方格組成的長方形。為了公平起見，
小明需要從這 NN 塊巧克力中切出 K 塊巧克力分給小朋友們。切出的巧克力需要滿足：
形狀是正方形，邊長是整數(shù);
大小相同;
例如一塊 6x5 的巧克力可以切出 6 塊 2x2 的巧克力或者 2 塊 3x3 的巧克力。
當然小朋友們都希望得到的巧克力盡可能大，你能幫小明計算出最大的邊長是多少么？
輸入描述
第一行包含兩個整數(shù) N,KN,K (1 \leq N, K \leq 10^51≤N,K≤10
5
)。
以下 N 行每行包含兩個整數(shù) H_i,W_iH
i
?
,W
i
?
(1 \leq H_i, W_i \leq 10^51≤H
i
?
,W
i
?
≤10
5
)。
輸入保證每位小朋友至少能獲得一塊 1x1 的巧克力。
輸出描述
輸出切出的正方形巧克力最大可能的邊長。
輸入輸出樣例
示例
輸入
2 10
6 5
5 6
copy
輸出
2
copy
運行限制
最大運行時間：1s
最大運行內存: 256M
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！
