当前位置：首页 > news >正文

2025CSP-J 冲刺训练(1)：二分

news 来源：原创 2025/8/22 17:07:34

2025CSP-J 冲刺训练 1

一、二分查找函数
- 1. 头文件
- 2. 前提条件
- 3. 功能函数
- 3.1 lower_bound
- 3.2 upper_bound
二、二分答案模板
- 1. 前提条件
- 2. 模板
三、典型例题
- 1. 寻找固定的和
- - 1.1 审题
  - 1.2 分析
  - 1.3 参考答案
- 2. Snuke Festival
- - 2.1 审题
  - 2.2 分析
  - 2.3 参考答案
四、拓展例题
- 1. 晒衣服
- - 1.1 审题
  - 1.2 分析
  - 1.3 参考答案
- 2. Chocolate Eating S
- - 2.1 审题
  - 2.2 参考答案

一、二分查找函数

1. 头文件

二分查找函数所在的头文件是算法头文件：

#include<algorithm>

2. 前提条件

传入的参数数组 a[] 必须是一个有序的数组，且一定是从小到大排列的。

3. 功能函数

3.1 lower_bound

lower_bound(a+1,a+n+1,val)-a;

程序	意义
`a+1`	起始位置指针
`a+n+1`	哨兵位置指针
`lower_bound()`	返回了一个指针
整体	返回 `a[]` 中第一个值 $\ge \tt val$ 的元素下标

3.2 upper_bound

功能：返回 a[] 中第一个值 $\tt val$ 的元素下标。

二、二分答案模板

1. 前提条件

题目要求直接求答案，且只能用枚举、暴力或者恶心的方法求解
检查一个答案很简单，且答案和限制条件是单调的

2. 模板

//最小值
while(l<r){//l+r可能溢出int mid=l+(r-l>>1);//mid=(l+r)/2if(check(mid))r=mid;else l=mid+1;
}
cout<<l;

//最大值
while(l<r){int mid=l+(r-l+1>>1);//mid=(l+r+1)/2if(check(mid))l=mid;else r=mid-1;
}
cout<<l;

三、典型例题

1. 寻找固定的和

1.1 审题

给出两个数组 x[]、y[] 和一个整数 $k$ ，每次从两个数组中各自取出一个数 $x_i$ 和 $y_j$ ，要求满足 $x_i+y_j=k$ 。已经取出过的数不能再取，问最多可以取出几对数？

1.2 分析

根据特性可知， $[$ a[lower_bound(a+1,a+n+1,val)-a] $,$ a[upper_bound(a+1,a+n+1,val)-a] $)$ 的范围中所有的数字都是 $\tt val$ 。则可以使用 a[upper_bound(a+1,a+n+1,val)-a] $-$ a[lower_bound(a+1,a+n+1,val)-a] 来计算 $\tt val$ 有多少个。

1.3 参考答案

$60$ 分代码（未考虑 x[]、y[] 的重复）：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+8;
int n,k,x[MAXN],y[MAXN];
int main(){cin>>n>>k;for(int i=1;i<=n;i++)cin>>x[i];for(int i=1;i<=n;i++)cin>>y[i];//二分函数要保证序列有序，所以要先排序sort(x+1,x+n+1);sort(y+1,y+n+1);long long ans=0;for(int i=1;i<=n;i++)//遍历一遍x[]中所有的元素ans+=upper_bound(y+1,y+n+1,k-x[i])-lower_bound(y+1,y+n+1,k-x[i]);//获取y[]中所有和x[i]相加为k的元素cout<<ans;return 0;
}

$100$ 分代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+8;
int n,k,x[MAXN],y[MAXN];
int main(){cin>>n>>k;for(int i=1;i<=n;i++)cin>>x[i];for(int i=1;i<=n;i++)cin>>y[i];sort(x+1,x+n+1);sort(y+1,y+n+1);long long ans=0;for(int i=1;i<=n;i++)if(x[i]!=x[i-1])//x第一次出现ans+=min(upper_bound(y+1,y+n+1,k-x[i])-lower_bound(y+1,y+n+1,k-x[i]),upper_bound(x+1,x+n+1,x[i])-lower_bound(x+1,x+n+1,x[i]));cout<<ans;return 0;
}

if 的判断可以有效地筛去 x[] 中重复的数值。
min 函数的第一个参数表示 y[] 中所有的 k-x[i]。
min 函数的第二个参数表示 x[] 中所有的 x[i]。
因为每个数字不能重复取出，所以取一个最小值。
如果实在看不懂，可以看看这个样例： $k=22,x_i=10,y=\{12, 12, 12, 12, 12\}$ 很显然，按照 $60$ 分的代码，我们算作了 $5$ 对，这样 $10$ 就会被重复取出。所以取它们重复个数的最小值算作最大的对数。

2. Snuke Festival

2.1 审题

今年音乐节，CCF（别问我为什么是 CCF）开始准备舞台。舞台由上中下 $3$ 部分组成。舞台 $3$ 个部分的零件分别有 $N$ 个，编号为 $1\sim N$ 。第 $i$ 个上部、中部、下部零件的尺寸分别为 $A_i,B_i,C_i$ 。为了组成一个舞台，中部零件的尺寸必须比上部零件尺寸大，下部零件的尺寸必须比中部零件尺寸大。CCF 能够组成多少个不同的舞台? 相同的舞台是指上中下部编号对应相等的舞台。

2.2 分析

说人话，这道题目就是：
给定三个长度为 $n$ 的数组 $A, B, C$ ，找出所有满足 $A_i<B_j<C_k$ 的数字，且三个数字之前都未被使用。

2.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,a[MAXN],b[MAXN],c[MAXN];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=n;i++)cin>>c[i];sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);long long ans=0;for(int i=1;i<=n;i++){//遍历所有的b[i]int cnta=lower_bound(a+1,a+n+1,b[i])-(a+1);int cntc=(c+n+1)-upper_bound(c+1,c+n+1,b[i]);ans+=1ll*cnta*cntc;}cout<<ans;return 0;
}

四、拓展例题

1. 晒衣服

1.1 审题

一件衣服在自然条件下用一秒的时间可以晒干 $a$ 点湿度。抠门的熊大妈只买了一台烘衣机。使用用一秒烘衣机可以让一件衣服额外烘干 $b$ 点湿度（一秒晒干 $a + b$ 湿度），但在同一时间内只能烘一件衣服。现在有 $n$ 件衣服，第 $i$ 衣服的湿度为 $w_i$ （保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 $0$ 为干）。

1.2 分析

详见注释。

1.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+8;
int n,a,b,w[MAXN];
bool check(int ans){int cnt=0;for(int i=1;i<=n;i++){int done=ans*a;//计算使用烘干机后的湿度int rem=w[i]-done;//计算剩余湿度if(rem>0)cnt+=(rem+b-1)/b;//计算需要额外烘干的次数}return cnt<=ans;
}
int main(){cin>>n>>a>>b;int l=0,r=0;for(int i=1;i<=n;i++)cin>>w[i],r=max(r,(w[i]-1)/a+1);//r:计算最大烘干次数while(l<r){int mid=l+(r-l>>1);if(check(mid))r=mid;else l=mid+1;}cout<<l;return 0;
}

2. Chocolate Eating S

2.1 审题

Bessie 收到了来自公牛们的 $N$ （ $1\le N\le50,000$ ）块巧克力，但她不想吃得太快，所以她想要为接下来的 $D$ （ $1\le D\le 50,000$ ）天制定一个吃巧克力的计划，以最大化她在这段时间内的最小幸福值。
Bessie 的幸福值是一个整数，初始为 $0$ ，每天晚上睡觉时会减半（如果需要，向下取整）。然而，当她吃第 $i$ 块巧克力时，她的幸福值会增加整数 $H_i$ （ $1\le H_i\le1,000,000$ ）。如果她在某一天吃巧克力，她这一天的幸福值被认为是吃完巧克力后的幸福值。Bessie 坚持要按照她收到巧克力的顺序来吃。
如果存在多个最优解，输出其中任意一个即可。
考虑一个例子，Bessie 需要在 $5$ 天内吃 $5$ 块巧克力，它们分别带来的幸福值为（ $10$ ， $40$ ， $13$ ， $22$ ， $7$ ）。
如果 Bessie 在第一天吃第一块巧克力（幸福值 $10$ ），然后等待吃其他的巧克力，她在第一天的幸福值是 $10$ 。
最小的睡前幸福值是 $24$ ，这是 Bessie 能做到的最优结果。

2.2 参考答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=5e4+8;
int n,d,h[MAXN],t[MAXN];
bool check(ll ans, bool record){ll id=0,sum=0;for(int i=1;i<=d;i++,sum>>=1)while(sum<ans){if(id>n)return false;sum+=h[id];if(record)t[id]=i;id++;}return true;
}
int main(){cin>>n>>d;for(int i=1;i<=n;i++)cin>>h[i];ll l=0,r=5e10;while(l<r){ll mid=l+(r-l+1>>1);if(check(mid,false))l=mid;else r=mid-1;}cout<<l<<endl;check(l,true);for(int i=1;i<=n;i++)cout<<(t[i]?t[i]:d)<<endl;return 0;
}

2025CSP-J 冲刺训练 1

一、二分查找函数

1. 头文件

2. 前提条件

3. 功能函数

3.1 lower_bound

3.2 upper_bound

二、二分答案模板

1. 前提条件

2. 模板

三、典型例题

1. 寻找固定的和

1.1 审题

1.2 分析

1.3 参考答案

2. Snuke Festival

2.1 审题

2.2 分析

2.3 参考答案

四、拓展例题

1. 晒衣服

1.1 审题

1.2 分析

1.3 参考答案

2. Chocolate Eating S

2.1 审题

2.2 参考答案

相关文章：