复兴无基础第二十三课 二分答案
2025-10-31 12:59:01
发布于：上海
15阅读
0回复
0点赞
T1【二分答案】 砍树
#include <iostream>
using namespace std;
int main(){
int n, m;
int tree[1000005];
cin >> n >> m;
for(int i = 1;i <= n; i++){
//输入每棵树的高度
cin >> tree[i];
}
int height = 0;
for(int i = 1;i <= n; i++){
if(tree[i] > height){
height = tree[i];
}
}
int left = 0, right = height, mid, ans;
while(left <= right) {//二分框架
mid = (left + right) / 2;
//计算高度mid时能锯的木材
long long sum = 0;
for(int j = 1;j <= n; j++){
if(tree[j] > mid) {
sum += tree[j] - mid;
}
}
//判断是否达到要求的木材m
if(sum >= m){
ans = mid;
left = mid + 1;
} else right = mid - 1;
}
cout << ans;
return 0;
}
T2数列分段
#include <iostream>
using namespace std;
int A[100005], N, M;
int main() {
cin >> N >> M;
int l = 0, r = 0, ans = 0;
for (int i = 1; i <= N; i++) {
cin >> A[i];
l = max(l, A[i]);
r += A[i];
}
while (l <= r) {
int mid = (l + r) / 2;
int sum = 0, cnt = 1;
for(int i = 1; i <= N; i++){
if(sum + A[i] <= mid){
sum += A[i];
}else{
sum = A[i];
cnt ++;
}
}
if (cnt <= M) {
r = mid - 1;
ans = mid;
}else{
l = mid + 1;
}
}
cout << ans;
return 0;
}
T3木材加工
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int a[maxn];
int n, k;
bool check(int mid) {
long long num = 0;
for (int i = 1; i <= n; i++) {
num += a[i] / mid;
}
return num >= k;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int l = 1, r = 1e9, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
ans = mid;
}
else {
r = mid - 1;
}
}
cout << ans;
return 0;
}
T4蛋糕
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n , k;
int x[100010] , y[100010];
bool check(int len)
{
int ans = 0;
for(int i = 1; i <= n; i++)
ans += (x[i] / len) * (y[i] / len);
return ans >= k;
}
int main()
{
//1、定义变量n,k,进行输入
cin >> n >> k; //n个蛋糕 k个人
//2、定义变量l,r,mid,ans。l,r为答案的极值，ans记录答案
int l = 1 , r = 0 , mid , ans;
//3、输入每个蛋糕的尺寸，同时求r
for(int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i]; //第i个蛋糕的尺寸
r = max(r , min(x[i] , y[i]));
}
//4、二分答案
while(l <= r)
{
//4.1、找到中间值mid，每个人获得的蛋糕的大小为mid
mid = (l + r) >> 1;
//4.2、求分的蛋糕数量,若数量大于等于k,符合题意，记录答案，更改左区间，求更优值
if(check(mid))
{
ans = mid;
l = mid + 1;
} //4.3、若数量小于k,每个人无法保证分得一块蛋糕,蛋糕的大小太大，更改右区间，减小蛋糕的大小
else
r = mid - 1;
}
//5、输出答案
cout << ans;
return 0;
}
T5进击的奶牛
#include<iostream>
#include<algorithm>
using namespace std;
int n , c;
int pos[100010];
bool check(int x)
{
int sum = 1 , xf = pos[1];
for(int i = 2; i <= n; i++)
{
if(pos[i] - xf >= x)
{
sum++;
xf = pos[i];
}
}
return sum >= c;
}
int main()
{
//1、定义变量n,c,进行输入
cin >> n >> c; //n个牛棚 c头牛
//2、输入n个牛棚的坐标
for(int i = 1; i <= n; i++)
cin >> pos[i]; //第i个牛棚的坐标
//3、牛棚的位置从小到大排序
sort(pos + 1 , pos + 1 + n);
//4、定义变量l,r,mid,ans，l和r为相邻两头牛之间距离的极值,ans保留答案
int l = 1 , r = pos[n] - pos[1] , mid , ans;
//5、二分答案
while(l <= r)
{
//5.1、找到中间值mid,相邻两头牛之间的距离不小于mid
mid = (l + r) / 2;
//5.2、看在mid的情况下，能放置的牛的数量，若数量大于等于c,记录答案, 更改左区间，让最近距离变大
if(check(mid))
{
ans = mid;
l = mid + 1;
}
else //5.3、若数量小于c,无法保证放置c头牛,更改右区间,减小最近距离
r = mid - 1;
}
//6、输出答案
cout << ans;
return 0;
}
T6跳石头
#include<iostream>
#include<algorithm>
using namespace std;
int L , n , m;
int d[50010];
bool check(int x)
{
int sum = 0;
for(int i = 0; i <= n; i++)
{
int j = i;
while(j <= n + 1 && d[j] - d[i] < x) //找到合适的岩石，保证跳跃的距离不低于x
j++;
sum += j - i - 1; //i~j移走的岩石数量
i = j - 1;
}
return sum <= m;
}
int main()
{
//1、定义变量L,n,m,进行输入
cin >> L >> n >> m; //起点到终点的距离 岩石数量 至多移走的岩石数量
//2、输入每个岩石到起点的距离
for(int i = 1; i <= n; i++)
cin >> d[i]; //第i块岩石到起点的距离
d[n + 1] = L;
//3、定义变量l,r,mid,ans，l和r为跳跃距离的极值,ans记录答案
int l = 1 , r = L , mid , ans;
//4、二分答案
while(l <= r)
{
//4.1、找到中间值mid,即跳跃的距离不低于mid
mid = (l + r) / 2;
//4.2、看在mid的情况下，能移走的石头的数量，若数量小于等于m,记录答案,更改左区间,让跳跃的距离变大
if(check(mid))
{
ans = mid;
l = mid + 1;
}
else //4.3、若数量大于m，更改右区间，减小跳跃的距离
r = mid - 1;
}
//5、输出答案
cout << ans;
return 0;
}
有帮助，赞一个