蓝桥杯2022年第十三届决赛真题-卡牌（二分答案）

1475 阅读 1 评论 0 点赞

原题链接：蓝桥杯2022年第十三届决赛真题-卡牌

解题思路：
直接二分，注意cheak函数的写法。
```cpp
bool cheak(int x) {
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if (x - t[i].a <= t[i].b) {
			ans += max(0, x - t[i].a);
		} else return 1;
	}
	if (m - ans >= 0) return 0;
	return 1;
}
```
完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
ll n, m;
struct node {
	int a, b, i;
} t[N];
bool cmp(node a, node b) {
	if (a.a == b.a) return a.b < b.b;
	return a.a < b.a;
}
bool cheak(int x) {
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if (x - t[i].a <= t[i].b) {
			ans += max(0, x - t[i].a);
		} else return 1;
	}
	if (m - ans >= 0) return 0;
	return 1;
}
int find(int l, int r) {
	int mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (cheak(mid)) r = mid - 1;
		else l = mid + 1;
	}
	return l - 1;
}
main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) scanf("%d", &t[i].a);
	for (int i = 1; i <= n; i++) scanf("%d", &t[i].b);
	for (int i = 1; i <= n; i++) t[i].i = i;
	sort(t + 1, t + n + 1, cmp);
	int an = find(t[1].a, 900000);
	if (an == 0) {
		cout << t[1].a;
		return 0;
	}
	cout << an;
	return 0;
}
```

0.0分

6 人评分

本文分类：题解列表
浏览次数：1475 次浏览
发布日期：2023-03-18 12:40:58
本文链接：https://blog.dotcpp.com/a/94989

上一篇 > 挑战最短代码
下一篇 > 蓝桥杯2022年第十三届决赛真题-最大数字（搜索+贪心）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2022年第十三届决赛真题-卡牌（二分答案）

评论列表共有 1 条评论

发表评论取消回复

蓝桥杯2022年第十三届决赛真题-卡牌（二分答案）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

评论列表共有 1 条评论

发表评论取消回复