C++ 代码(自己随手写的)
#include<iostream>
#include<vector>
using namespace std;
vector<pair<int,int>> A; //这里用pair对组来储存的每块巧克力的规格,长和宽
int N,K;
bool check(int mid) // 二分的条件判断
{
int cnt = 0;
for(auto a : A) //C++11 的range_for语法更简洁
{
int x_end = a.first, y_end = a.second, x = 0; //取得大块巧克力的长 和 宽
for(int i = 0; i < y_end / mid ; ++i) //for循环的次数其实为 宽 / 小块巧克力的宽 --》 表示可以循环几层
{
while(x <= x_end) //此时 x 小于 大巧克力的长继续添加
{
x += mid;
if(x <= x_end) cnt++;
else //此时超过了大块巧克力的长,表示这层不能在增加
{
x = 0; //这里 x = 0 是为了下一次的for做的初始化
break; //break跳出的是判断当前层的 while
}
}
}
}
return cnt >= K;
}
int main()
{
cin >> N >> K;
int a, b;
for(int i = 0; i < N; ++i)
{
cin >> a >> b;
A.push_back({a,b});
}
int l = 1, r = 1e+5, mid;
while(r > l)
{
mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << r << endl;
return 0;
}
#### 基本思路
其实这道题和昨天分绳子的题目类似,都是求一个最优解的问题,这里如果直接求最优解肯定不好求
故这里采用如分绳子一样的思路 --> 二分的思想, 如何二分是这道题的关键 --》 将最优解问题
转化为二分的条件判断。 从题目入手,题目要求将巧克力分给K个人,即将巧克力分为 K 份, 故同样假设
此时每人分得的巧克力长和宽为x(题目要求分得的巧克力为正方形,边长为整数),故每块大的巧克力中
可以分出多少块面积为 x*x 的小巧克力,然后求和得到手上巧克力总共可以分得最多的份数。这个问题相比
直接最优解有思路多了。 然后根据此时求得的最多份数 与 题目要求的 K 作比较,如果比 K 大,说明 x 偏小了
巧克力还可以更大些, 如果比 K 小, 说明此时小块巧克力的面积偏大了,需要减少来分到K份。
##### 注意事项
由于题目要求的巧克力的边长是一个整数,故该题是一个整数二分的题目,故就需要注意边界问题
对于整数二分, 当更新条件为 l = mid , r = mid - 1的时候此时mid的二分要写成 mid = l + r + 1 >> 1;
因为 l + r >> 1 属于下取整,即当只有两个数的时候会取到左边的数,而 l = mid; 这个写法则会使得区间
并没有得到更新
参考y总的代码后再结合自己的改进
#include<iostream>
#include<vector>
using namespace std;
using LL = long long; //这里由于一块巧克力的H, W的大小最大可能为10的五次方,最多可能有10的10次方小块,这里为了防止爆int,故使用Long long
int N,K;
vector<pair<int,int>> A;
bool check(int mid)
{
LL cnt = 0;
for(auto a : A)
cnt += static_cast<LL>((a.first / mid) * (a.second / mid)); //这一步计算此时分得的小的巧克力数写得很简单 这里使用的是C++风格的强制类型转换
return cnt >= K;
}
int main()
{
cin >> N >> K;
int a,b;
for(int i = 0; i < N ; ++i)
cin >> a >> b, A.push_back({a,b});
int l = 1, r = 1e+5, mid;
while(r > l)
{
mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << r << endl;
return 0;
}