X02-Day03-代码笔记
2024-07-25 18:17:34
发布于：北京
204阅读
0回复
0点赞
// 二分基础模板 - 找数
#include <iostream>
#include <algorithm>
using namespace std;
// 二分算法： 在有序的状态下，快速地找到目标值
int a[10] = {0, 1, 1, 3, 3, 3, 4, 7, 9};
int n;
int main () {
n = 8; // 1 ~ 8 的元素
int x = 4; // 查找的目标
// 若无序，还得先排序
int L = 1, R = n; // 左右游标
int ans = -1;
while (L <= R) {
// 1. 计算中点
int mid = (R + L) / 2;
// 2. 分类判断
if (a[mid] > x) { // a[mid] 太大
R = mid - 1;
} else if (a[mid] < x) { // a[mid]太小
L = mid + 1;
} else {
ans = mid; // 找到并记录
printf("找到了，位置 %d, 值 %d\n", mid, a[mid]);
break;
}
}
if (ans == -1) {
cout << "没找到" << endl;
}
return 0;
}
// 第一个大于等于
#include <iostream>
#include <algorithm>
using namespace std;
// 二分算法： 在有序的状态下，快速地找到目标值
int a[10] = {0, 1, 1, 3, 3, 3, 4, 7, 9};
int n;
int main () {
n = 8; // 1 ~ 8 的元素
int x = 2; // 查找的目标
// 若无序，还得先排序
int L = 1, R = n; // 左右游标
int ans = -1;
while (L <= R) {
// 1. 计算中点
int mid = (R + L) / 2;
printf("%d %d %d %d\n", L, R, mid, a[mid]);
// 2. 分类判断
if (a[mid] > x) { // a[mid] 太大
ans = mid; // 也可能是第一个大于 x 的地方
R = mid - 1;
} else if (a[mid] < x) { // a[mid]太小
L = mid + 1;
} else { // ==
ans = mid; // 找到并记录
R = mid - 1;
}
}
cout << ans << endl;
return 0;
}
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int H[N];
int n, m;
// 需要知道 h 这个高度，是否满足 m 的需求
bool check (ll h) {
ll sum = 0;
for (int i = 1; i <= n; i ++) {
if (H[i] > h) { // 树高 > 砍伐
sum += H[i] - h;
// 累加获得的木材
}
}
if (sum > m) {
// 足够了，需要再高一些
return true;
} else if (sum < m) {
// 不够，需要矮一些
return false;
} else {
// 相等，也是足够，再高一些
return true;
}
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
cin >> H[i];
}
ll L = 0, R = 1e9;
ll ans = -1;
while (L <= R) {
ll mid = (L + R) / 2;
// mid 是砍伐高度
if ( check(mid) == true ) {
// 答案在这里出现 >= m
ans = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
cout << ans << endl;
return 0;
}
Day04 👉 https://www.acgo.cn/discuss/study/22281
有帮助，赞一个