题目
题目链接
题解二分。
想到二分比实现二分要难点。
可行解部分可以与不可行解部分完美地分隔开来。
绿色部分是分成的巧克力比较小时都可以满足,而大于一定程度的时候就不可行了。
所以可以将其抽象成小于可行,大于不可行的二分问题。
在判断时,遍历全部巧克力,每个巧克力分割成的小巧克力数相加。分割成的小巧克力数目的计算方式为,高整除枚举到的 x x x,宽整除枚举到的 x x x的乘积。
代码//
#include
using namespace std;
const int N = 1e5+10;
int n, k, mx = 0;
int h[N], w[N];
bool check (int x) {
int res = 0;
for (int i = 1;i = k;
}
int main()
{
cin >> n >> k;
for (int i = 1;i > h[i] >> w[i],
mx = max (mx, max(h[i], w[i])); // 记录的应该是最大值,因为就算小巧克力一块也切不出来也无所谓
int l = 1, r = mx, mid;
while (l > 1;
if (check (mid)) l = mid;
else r = mid - 1;
}
cout
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?