有基础班_第十课_二分答案（二）
2025-06-15 16:33:12
发布于：上海
2阅读
0回复
0点赞
| 题目 |
|---|
| 进击的奶牛 |
| 跳石头 |
| 午枫爱搬家 |
| 探险 |
| Kingdom Game I |
| 勇敢的冒险者 |
进击的奶牛
题目大意
给定一个一维坐标系上的 个牛棚位置，编号为 ，你要在这些位置中安排 头牛。要求这些牛必须分配到不同的牛棚，且任意两头牛的最近距离尽可能大。
请你求出，在最优安排下，这个“最近的两头牛的最小距离”的最大值。
题意分析
这是一个经典的“最大化最小值”类型问题：
- 所有牛必须放进牛棚（数量不够是不合法的）；
- 安排时，要求任意两头牛之间的最近距离尽可能大；
- 我们要最大化这个最近距离的最小值。
解题思路
本题可以使用 二分答案 + 贪心判断 来求解。
1. 二分答案
- 设我们要找的答案为 ：所有牛之间的最近距离不小于 。
- 我们对 进行二分查找，枚举可能的最近距离 ，检查是否可行。
2. 贪心验证（check 函数）
- 将牛棚的位置排序；
- 然后从最左边开始放牛，尽可能让每头牛之间的距离 ≥ ；
- 如果能放下 头牛，说明当前 可行。
时间复杂度分析
- 排序：；
- 二分次数：最多 ，约为 30；
- 每次 check：线性扫一遍 个牛棚，；
- 总复杂度为 ， 为最大距离。
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int n, c; // n个牛棚，c头牛
int pos[MAXN]; // 牛棚的位置
// 检查能否使任意两头牛之间的最小距离 ≥ x，且安排下c头牛
bool check(int x) {
int count = 1; // 第1头牛放在第一个牛棚
int last_pos = pos[1]; // 上一头牛的位置
for (int i = 2; i <= n; i++) {
if (pos[i] - last_pos >= x) {
count++; // 放下一头牛
last_pos = pos[i]; // 更新上一头牛的位置
}
}
return count >= c;
}
int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> pos[i];
}
sort(pos + 1, pos + 1 + n); // 坐标排序
int l = 1, r = pos[n] - pos[1], ans = 0;
// 二分最小距离的最大值
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid; // 当前mid可行，更新答案
l = mid + 1; // 尝试更大的最小距离
} else {
r = mid - 1; // 当前mid不可行，尝试更小的最小距离
}
}
cout << ans << endl;
return 0;
}
跳石头
题目大意
给定一个总长为 的河流，起点为 ，终点为 ，中间有 块岩石，每块岩石的位置为 （满足 ，已升序给出）。
你可以最多移除 块岩石，目的是使得最终从起点跳到终点所经过的每一跳中，最短的跳跃距离尽可能大。
输出在最优移除策略下，这个“最短跳跃距离”的最大可能值。
题意分析
这是一道典型的“最大化最小值”类型的问题。我们需要在跳跃过程中最大化最短跳跃距离，而要做到这一点，就必须利用二分答案 + 贪心判断的套路：
- 最大化最小跳跃距离 二分答案；
- 是否能移除 ≤ M 块石头，使得每次跳跃距离都 ≥ x？ 贪心 check。
解题思路
Step 1: 二分答案
我们要找一个最大的 ，使得在移除不超过 块岩石后，跳跃过程中每一跳的距离都不少于 。
- 答案范围是 ；
- 用二分法枚举这个 ；
- 每次二分中间值 mid 后，判断是否能在跳跃过程中保证最短跳跃距离 ≥ mid；
- 如果可以，就尝试更大的 mid；
- 如果不行，就尝试更小的 mid。
Step 2: 贪心判断 check(mid)
我们从起点开始向终点跳：
- 每次尽量跳到“最远但距离不小于 mid 的岩石”；
- 如果当前位置到下一个岩石的距离 < mid，就必须移除这个岩石；
- 贪心地尝试跳远，统计移除了多少块石头；
- 最终判断移除的数量是否 ≤ M。
时间复杂度分析
- 二分次数最多 ；
- 每次 check 遍历所有岩石一次，；
- 整体时间复杂度为 ，对于 、 可以接受。
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 50010;
int L, N, M;
int d[MAXN]; // 岩石的位置
// 判断是否可以让每次跳跃距离 ≥ x，且移除石头数量 ≤ M
bool check(int x) {
int remove_cnt = 0; // 记录移除的岩石数量
int last_pos = 0; // 上一次跳跃的位置（起点）
for (int i = 1; i <= N + 1; i++) {
if (d[i] - last_pos < x) {
// 当前岩石离得太近，需要移除
remove_cnt++;
} else {
// 否则从当前岩石起跳
last_pos = d[i];
}
}
return remove_cnt <= M;
}
int main() {
cin >> L >> N >> M;
// 输入所有岩石的位置
for (int i = 1; i <= N; i++) {
cin >> d[i];
}
// 将终点作为第 N+1 块“岩石”
d[N + 1] = L;
// 二分答案
int l = 1, r = L, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid; // 可行，尝试更大的最小距离
l = mid + 1;
} else {
r = mid - 1; // 不可行，减小跳跃距离
}
}
cout << ans << endl;
return 0;
}
午枫爱搬家
题目大意
给定 个物品的重量，按照顺序搬运，最多搬 次。每次搬的物品总重量不能超过某个上限 。要求求出使得在最多搬 次的前提下，该最大重量上限 的最小值。
题意分析
这是一个经典的「最小化最大值」问题 —— 把 个物品顺序分成 段，每段的总和不超过某个值 ，求满足条件的最小 。
可以使用 二分答案 + 贪心判断 来解决。
解题思路
- 二分上限 的值，下限为最大单个物品的重量，上限可以设得较大，例如 。
- 贪心判断是否可行：
- 从前往后搬物品，如果当前搬运重量加上一个物品超过了当前尝试的 ，就开始新的一次搬运。
- 如果搬运次数不超过 次，则当前的 是可行的。
- 更新答案：
- 如果当前 可行，就尝试更小的 ；
- 否则增大 。
时间复杂度解析
- 二分查找复杂度为 ，最多约 次；
- 每次
check是 ； - 总体复杂度为 ，对于 是可以接受的。
代码演示
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 2e5 + 5;
ll n, k;
ll a[MAXN];
// 判断是否可以在最大和不超过 x 的条件下，分成不超过 k 段
bool check(ll x) {
ll cnt = 1, sum = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > x) return false; // 单个物品太重，肯定不行
if (sum + a[i] <= x) {
sum += a[i];
} else {
cnt++; // 开始新的一次搬运
sum = a[i]; // 新一轮的搬运从当前物品开始
}
}
return cnt <= k;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
ll l = 1, r = 1e14, ans = r;
while (l <= r) {
ll mid = (l + r) / 2;
if (check(mid)) {
ans = mid; // mid 可行，尝试更小值
r = mid - 1;
} else {
l = mid + 1; // mid 不可行，需要更大值
}
}
cout << ans << endl;
return 0;
}
探险
题目大意
有 个探险队员，每个队员的体力值为 ，要将他们分为 个连续的小组。你需要将所有人分完，且每组必须连续排列。请你设计一种分组方式，使得所有组中体力和最小的一组的体力和最大。
输出这个最大值。
题意分析
- 分组必须是连续的（不能随意选择某几个）。
- 所有人必须分组，不可遗漏。
- 目标是最大化所有组中体力和最小的一组的值。
- 实质是一个“最大化最小值”的问题。
解题思路
这个问题可以通过二分答案 + 贪心验证解决：
- 设定一个答案范围：我们设最小体力和为 ，想知道是否能划分出 个小组，每组体力和 ≥ 。
- 二分搜索：对 进行二分查找，寻找最大可行值。
- 贪心验证 check(x)：
- 顺序遍历每个人的体力值，累计小组和。
- 当累计和 ≥ ，就认为当前一组划分完毕，重置累计和。
- 最终统计划分出的组数是否 ≥ ，若是，说明当前 可行。
时间复杂度解析
- 二分搜索复杂度：，最多为
- 每次 check 复杂度：，需要线性遍历整个数组
- 总体复杂度：，足以应对
代码演示
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 3e4 + 34;
ll n, k;
ll a[MAXN];
// 检查是否可以划分成 >= k 组，每组体力和 ≥ mid
bool can(const ll &mid) {
ll res = 0, sum = 0;
for (ll i = 1; i <= n; i++) {
sum += a[i];
if (sum >= mid) {
res++; // 当前一组划分成功
sum = 0; // 重置累计和，开始新的一组
}
}
return res >= k;
}
int main() {
cin >> n >> k;
for (ll i = 1; i <= n; i++) cin >> a[i];
ll l = 0, r = 1e9, ans = 0;
while (l <= r) {
ll mid = (l + r) >> 1;
if (can(mid)) {
ans = mid; // mid 可行，尝试更大的
l = mid + 1;
} else {
r = mid - 1; // mid 不可行，尝试更小的
}
}
cout << ans << endl;
return 0;
}
Kingdom Game I
题目大意
给出 个居民，每人有生活成本 和对王国的贡献 。
若居民被分配的生活成本 小于 ，他会叛乱，对王国造成 的负贡献（变成 ）；
若 ，他对王国的正面贡献变为 ，其中 。
问：最小的 （每个人都分配一样的 ）是多少，使得总贡献 不小于 ？
题意分析
每个人的贡献函数关于 是分段函数：
- 当 ，贡献是
- 当 ，贡献是
目标是找到最小的 ，使得总贡献 。
解题思路
二分答案：
- 的最小值为 ，最大可以设为 （显然超过所有 ）。
- 每次取中间值 mid：
- 计算对于所有人，以 时的总贡献值；
- 若总贡献 ，说明当前 是可行解，尝试更小；
- 否则增大 。
check 函数逻辑：
if (S < w_i) → 贡献为 -v_i
else → 贡献为 floor(S / w_i) * v_i
时间复杂度解析
- 二分查找次数：
- 每次 check 遍历 个人，总共约 次操作。
- 对于 是可以接受的。
代码演示
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
long long n, m;
// 定义结构体保存生活成本 w 和贡献 v
struct Node {
long long w, v;
} a[MAXN];
// 检查当每人分配的生活成本为 x 时，总贡献是否 >= m
bool check(long long x) {
long long sum = 0;
for (int i = 1; i <= n; i++) {
if (a[i].w <= x) {
// floor(x / w_i) * v_i
sum += (x / a[i].w) * a[i].v;
} else {
// 叛乱，造成负贡献
sum -= a[i].v;
}
}
return sum >= m;
}
int main() {
cin >> n >> m;
// 读取 w_i
for (int i = 1; i <= n; i++) {
cin >> a[i].w;
}
// 读取 v_i
for (int i = 1; i <= n; i++) {
cin >> a[i].v;
}
long long left = 0, right = 1e9 + 7, answer = -1;
// 二分搜索最小的 S
while (left <= right) {
long long mid = (left + right) / 2;
if (check(mid)) {
answer = mid;
right = mid - 1; // 尝试更小的 S
} else {
left = mid + 1; // 贡献不足，增大 S
}
}
cout << answer << endl;
return 0;
}
勇敢的冒险者
题目大意
一个人站在数轴的 0 点，每次跳跃可以选择：
- 向前跳 （第 次跳跃时）
- 向后跳 1
第 次跳跃的前跳步数是 ，而后跳始终是 。问：最少需要多少次跳跃，才能到达目标位置 （）？
题意分析
每次跳跃有两个选择，但显然：
- 多数时候我们优先前跳，速度更快
- 如果前跳过头了，可以用 补回来
我们要求最小跳跃次数 ，使得从 出发，经过最多 步可以到达
解题思路
Step 1：前跳求和
设我们只使用前跳，总共跳 次，跳到的位置是：
这个是前 次的最大可能位置。
我们希望：
那么最小的 满足这个条件，是候选答案。
Step 2：考虑能否通过后跳调整
前跳总步数是 ，但我们可以在后面某些跳中选择 ，让总距离变为 。
也就是说，如果：
那么就可以通过把某个 换成 的方式，使得恰好跳到 。
把 换成 的过程，总共损失了 步，所以对任意，都有 使得 。
但如果：
无法调整出来（因为 时，）。
结论：
- 若 ，刚好跳到：答案是
- 若 且 ，可以通过换跳调整：答案是
- 若 ，不能调整，需要多跳 1 步：答案是
Step 3：使用二分找最小
我们要找到满足 的最小 ，可以用二分法来优化。
时间复杂度解析
- 每个测试用例：
- 二分 ：最多 次
- 时间复杂度为
- 总体复杂度：，对于 ，可接受
代码演示
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 计算前k次跳跃的距离和
ll getSum(ll k) {
return (1 + k) * k / 2;
}
int main() {
int t, x;
cin >> t;
while (t--) {
cin >> x;
int l = 1, r = x, ans = 0;
// 二分查找满足条件的最小跳跃次数
while (l <= r) {
int mid = (l + r) / 2;
if (getSum(mid) >= x) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
// 计算前ans次跳跃的距离和
ll s = getSum(ans);
// 根据 s 和 x 的差值判断是否需要多跳一步
if (s - x == 1) {
cout << ans + 1 << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
这里空空如也
有帮助，赞一个