reference
#include<iostream>
#include<cstring>
using namespace std;
/*使得將巧克力按照邊長maxX進行切分
，切分成的份數要大于等于K，
而如果按照maxX+1進行切割
，將不再能夠切出K塊，
如果從1-100000逐個查找，那么肯定超時，所以采用二分查找，
*/
int n,k,a[11000],b[110000];//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);//可以切割成的邊長合理的正方形巧克力的塊數
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 = 100000;
while(l<=r){
int m = l/2+r/2;
if(ok(m)){
l=m+1;
}else{
r=m-1;
}
}
cout<<l-1<<endl;
return 0;
}
題目描述
兒童節那天有 K 位小朋友到小明家做客，小明拿出了珍藏的巧克力招待小朋友們，
小明一共有 NN 塊巧克力，其中第 ii 塊是 H_i \times WiH
i
?
×Wi 的方格組成的長方形，為了公平起見，
小明需要從這 NN 塊巧克力中切出 K 塊巧克力分給小朋友們，切出的巧克力需要滿足：
形狀是正方形，邊長是整數;
大小相同;
例如一塊 6x5 的巧克力可以切出 6 塊 2x2 的巧克力或者 2 塊 3x3 的巧克力，
當然小朋友們都希望得到的巧克力盡可能大，你能幫小明計算出最大的邊長是多少么？
輸入描述
第一行包含兩個整數 N,KN,K (1 \leq N, K \leq 10^51≤N,K≤10
5
)，
以下 N 行每行包含兩個整數 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
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/415198.html
標籤：C++
上一篇：c++編程筆記
下一篇：一種 C++ 轉換的非正式分類