22软工孟姿好

用户名：dotcpp0669285

访问量：740

签　名：

莫道桑榆晚，为霞尚满天

等　　级
排　　名	878
经　　验	3562
参赛次数	13
文章发表	47
年　　龄	20
在职情况	学生
学　　校	bilibili大学
专　　业	软件工程

　　自我简介：

自强不息

TA的其他文章

旧物有情 # 枚举法求素数
浏览：22

旧物有情 # 枚举法求水仙花数
浏览：14

旧物有情 # 遍历求二维数组转置
浏览：9

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

二分 # 1885: 蓝桥杯2017年第八届真题-分巧克力(C++)

　　作者: 22软工孟姿好　　　　发表时间：2024-11-22 08:09:36 浏览：7　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-分巧克力

二分思路

最少切边长为1,最多切边长为1e5

如果我们切边长为MID的巧克力
可以满足切出来的巧克力数量 
大于等于 
小朋友的数量

那么我们可以尝试切>=MID的巧克力(收缩左边界)
看是否继续满足切出来的巧克力数量大于等于
小朋友的数量

如果不满足,那么我们收缩右边界

二分模板

```c++
//这是一套带有个人习惯的二分模板,不是死的
int mid = l + r + 1 >> 1;
if(check(mid))l=mid;
else r=mid-1;
//----------------------------

int mid = l + r >> 1;
if(check(mid))r=mid;
else l=mid+1;
```

```c++
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;
int h[N], w[N];
int n, k;

bool check(int mid) {
	//记录一下能分出来几个巧克力
	int res = 0;

for (int i = 0; i < n; i++) {
		res += (h[i] / mid) * (w[i] / mid);
	}
	
	if (res >= k)return true;

return false;
}

int main() {
	cin >> n >> k;

for (int i = 0; i < n; i++)cin >> h[i] >> w[i];
	
	int l = 1, r = 1e5;
	while (l < r) {
		int mid = l + r + 1>>1;
		if (check(mid))l = mid;
		else r = mid - 1;
	}

cout << r;

return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

22软工孟姿好

TA的其他文章

你可能喜欢

求圆的面积（C++代码）这里推荐使用宏定义

A+B for Input-Output Practice (VII) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

二分 # 1885: 蓝桥杯2017年第八届真题-分巧克力(C++)

评论区

精彩推荐

C语言训练-字符串正反连接（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-计算1977！* （C++代码）

输出正反三角形（C语言代码）格式错误！！！

字符串的输入输出处理（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

三角形（C++代码）递推

22软工孟姿好

TA的其他文章

你可能喜欢

求圆的面积 （C++代码）这里推荐使用宏定义

A+B for Input-Output Practice (VII) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

二分 # 1885: 蓝桥杯2017年第八届真题-分巧克力(C++)

评论区

精彩推荐

C语言训练-字符串正反连接 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-计算1977！* （C++代码）

输出正反三角形 （C语言代码）格式错误！！！

字符串的输入输出处理 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

三角形 （C++代码）递推

求圆的面积（C++代码）这里推荐使用宏定义

　　评论区

C语言训练-字符串正反连接（C语言代码）

输出正反三角形（C语言代码）格式错误！！！

字符串的输入输出处理（C语言代码）

C二级辅导-阶乘数列（C语言代码）

三角形（C++代码）递推