您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

2017年蓝桥杯B组C/C++省赛-分巧克力

不牌不改 发布时间:2022-03-15 10:49:11 ,浏览量:0

题目

题目链接

题解

二分。

想到二分比实现二分要难点。

可行解部分可以与不可行解部分完美地分隔开来。

在这里插入图片描述

绿色部分是分成的巧克力比较小时都可以满足,而大于一定程度的时候就不可行了。

所以可以将其抽象成小于可行,大于不可行的二分问题。

在判断时,遍历全部巧克力,每个巧克力分割成的小巧克力数相加。分割成的小巧克力数目的计算方式为,高整除枚举到的 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             
关注
打赏
1662186765
查看更多评论
0.0653s