复兴无基础第二十五课 二分答案（二）
2025-11-23 15:20:22
发布于：上海
0阅读
0回复
0点赞
T1爱吃香蕉的小码酱
#include<iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;// 定义数组的最大长度
int a[N], n, h; // n表示香蕉堆的数量，h表示时间限制，a数组存储每堆香蕉的数量
// 检查以速度k是否能在h小时内吃完所有香蕉
bool check( int k ) {
long long ans=0;
for(int i = 1; i <= n; i++) {
// 计算每堆香蕉需要的时间，向上取整
ans += (a[i] + k - 1) / k;
}
// 如果总时间小于等于h，则返回true，否则返回false
return ans <= h;
}
//二分答案求下界 __越小越好
int lower_answer(int l, int r){
int ans = 0;
while(l <= r) {
int mid = (l+r)/2;
if(check(mid)){//找到符合条件的，越小越好往左找 更新右端点
ans = mid;
r = mid-1;
}
else{//往右找 更新左端点
l = mid+1;
}
}
return ans;
}
int main(){
scanf("%d %d", &n, &h);// 输入香蕉堆数和时间限制
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
int l = 1, r = 1e9;// 最小可能的速度 1 最大可能的速度：每堆香蕉的数量最大值
cout << lower_answer(l, r);
return 0;
}
T2鱼缸
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, x;
// 验证h高度是否可行（总水量≤x）
bool check(long long h) {
long long sum = 0; // 使用long long防溢出（sum可能高达2e14）
for (int i = 1; i <= n; i++) {
if (a[i] < h) { // 仅当珊瑚高度不足h时才需加水
sum += h - a[i];
}
}
return sum <= x; // 判断是否满足水量约束
}
// 二分查找最大可行h
int upper_answer(long long l, long long r) {
int ans = 0; // 记录最大可行高度
while (l <= r) { // 标准二分框架
long long mid = (l + r) / 2;
if (check(mid)) { // 当前高度可行
ans = mid; // 更新候选答案
l = mid + 1; // 尝试更大的高度
} else {
r = mid - 1; // 超出水量限制，降低高度
}
}
return ans; // 返回最终找到的最大高度
}
int main() {
cin >> n >> x;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
// 二分范围：最小高度1，最大高度2e9（覆盖极端情况）
cout << upper_answer(1, 2e9);
return 0;
}
T3修学分
#include <bits/stdc++.h>
using namespace std;
long long n, l, t, p, d;
// 检查在 x 天学习的情况下，是否可以获得足够的积分
bool check(int x) {
// 计算最多可以完成的任务数
long long c1 = min(x * 2LL, d);
// 计算总积分
long long sum = c1 * t + x * l;
// 返回是否达到或超过所需积分
return sum >= p;
}
/* 二分答案求下界 答案越小越好 */
long long lower_answer(long long l, long long r) {
long long ans = 0;
while (l <= r) {
long long mid = (l + r) / 2; // 计算中间值
if (check(mid)) { // 如果在 mid 天学习可以达到或超过所需积分
ans = mid; // 更新答案
r = mid - 1; // 尝试减少学习天数
} else {
l = mid + 1; // 增加学习天数
}
}
return ans;
}
int main() {
// 读取输入
cin >> n >> p >> l >> t;
// 计算总共可以解锁的任务数
d = (n + 6) / 7;
// 二分查找的左右边界
long long l = 0;
long long r = n;
// 输出最大休息天数
cout << n - lower_answer(l , r);
return 0;
}
T4最后一个质数
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6+10;
int a[N];
// 质数判断函数
bool is_prime(int x) {
if(x < 2) return false;
for(long long i=2; i*i <= x; i++) {
if(x%i == 0) return false;
}
return true;
}
// 二分答案求上界
int upper_answer(int l, int r) {
int ans = 0;
while(l <= r) {
int mid = (l + r) / 2;
if(is_prime(a[mid])) {
ans = mid; // 记录有效位置
l = mid + 1; // 尝试寻找更右边的质数
} else {
r = mid - 1; // 非质数区域需向左收缩
}
}
return ans;
}
int main() {
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
cout << upper_answer(1, n);
return 0;
}
T5投票箱
#include<iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 5e5 + 10; // 最大城市数量
int a[N], n, m; // a[]存储城市人口，n为城市数，m为投票箱总数
/* 验证函数：判断当单个投票箱最大人数为k时，总箱数是否≤m */
bool check(int k) {
long long ans = 0; // 防止大数溢出
for(int i=1; i<=n; i++) {
// 向上取整技巧：(a + b - 1)/b = ceil(a/b)
// 计算该城市所需的最小投票箱数
ans += (a[i] + k - 1) / k;
}
return ans <= m; // 总箱数是否在预算范围内
}
/*二分答案求下界 __越小越好 */
int lower_answer(int l, int r) {
int ans = 0;
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid)) { // 当前 mid 可行，尝试更小的值
ans = mid; // 记录当前最优解
r = mid - 1; // 缩小右边界mid
} else { // 当前mid 不可行，必须增大
l = mid + 1; // 扩大左边界
}
}
return ans; // 返回最小可行解
}
int main() {
while(cin >> n >> m) {
// 输入终止条件
if(n == -1 && m == -1) return 0;
// 读取城市人口数据
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
// 二分边界：最小1人/箱，最大5e6人/箱（题目给定a_i上限）
int l = 1, r = 5000000;
// 优化点：也可计算max(a_i)缩小右边界
// 输出最优解
cout << lower_answer(l, r) << endl;
}
return 0;
}
T6卡牌
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N];
int n;
long long m;
//最多凑够x张牌
bool check(int x){
long long s = 0; //使用的空白牌的张数
for(int i = 1; i <= n; i++){
if(x - a[i] <= b[i]){
s += max(x - a[i], 0); //累计第 i 张牌使用了几张空白牌
} else { // x - a[i] > b[i] 说明要用的空白牌大于题目要求的b[i]的限制，说明没法凑出 x 张牌
return false;
}
}
if(s <= m) return true; //使用的空白牌的张数
else return false;
}
//二分答案求上界
int upper_answer(long long l,long long r){//l+r可能会超int
int ans=0;
while(l<=r) {
long long mid=(l+r)/2;
if(check(mid)){//找到符合条件的，你希望越大越好，往右找 更新左端点
ans=mid;
l=mid+1;
}else{//往左找 更新右端点
r=mid-1;
}
}
return ans;
}
int main(){
cin >> n >> m;
int l = 1e9, r = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
l = min(l, a[i]);
}
for(int j = 1; j <= n; j++) {
cin >> b[j];
r = max(r, b[j] + a[j]);
}
cout<< upper_answer(l,r);
return 0;
}
T7暴躁的病人
#include<iostream>
#include<algorithm>
using namespace std;
int n, c;
long long x[1000005];
bool check(long long d) {//d表示假设最大的最小距离是d
int lst = 1;//上一个病人所在病房的位置
int cnt = 1;//已经住了1个病人，也就是第一个病人一定住在第一个房间
for (int i = 2; i <= n; i++) {//枚举剩下的 n-1 个病房
if (x[i] - x[lst] >= d) {//如果和上一个病人所在的病房之间距离大于等于 d 了
lst = i;//那么这个病房可以住一个病人
cnt++;
}
}
if (cnt >= c) {//如果能够住下至少 C 个病人
return true;//那么答案成立
}
else {//否则不成立
return false;
}
}
int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
sort(x + 1, x + 1 + n);//别忘记排序
long long l = 0, r = 1e12;
long long ans = -1;
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) {//如果 mid 这个距离能够住下 C 个病人
ans = mid;
l = mid + 1;//那就看看能不能让最小距离更大一些
}
else {
r = mid - 1;//否则让最小距离更小
}
}
cout << ans << endl;
return 0;
}
这里空空如也
有帮助，赞一个