1. 查找 x 是否存在
思路简介
数组有序时，可以用二分查找。
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int n,x;
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
// 二分查找的左右边界
int l = 1, r = n;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] < x){
// 中间值比 x 小，说明 x 只可能在右边
l = mid + 1;
}else if(a[mid] > x){
// 中间值比 x 大，说明 x 只可能在左边
r = mid - 1;
}else{
// 找到 x，输出下标
cout << mid;
return 0;
}
}
// 循环结束还没找到，说明不存在
cout << -1;
return 0;
}
2. 手写 lower_bound：查找第一个 >= x 的位置
思路简介
要找的是第一个满足：
a[i] >= x
的位置。
二分时，如果：
a[mid] >= x
说明 mid 可能是答案，但是前面可能还有更靠左的答案，所以：
ans = mid;
r = mid - 1;
如果：
a[mid] < x
说明 mid 和左边都太小了，所以往右找：
l = mid + 1;
如果不存在，输出 n + 1。
带注释代码
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int n,x,q;
int main(){
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
while(q--){
cin >> x;
int l = 1, r = n;
// ans 表示第一个 >= x 的位置
// 如果找不到，默认是 n + 1
int ans = n + 1;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] >= x){
// a[mid] 已经满足 >= x
// 先记录答案
ans = mid;
// 但题目要第一个位置，所以继续往左找
r = mid - 1;
}else{
// a[mid] < x，说明 mid 和左边都不满足
// 只能往右找
l = mid + 1;
}
}
cout << ans << endl;
}
return 0;
}
3. STL lower_bound：第一个 >= x
思路简介
lower_bound 的含义是：
找第一个大于等于 x 的位置
写法：
lower_bound(a + 1, a + n + 1, x)
返回的是地址。
要转成下标，需要减去数组首地址：
lower_bound(a + 1, a + n + 1, x) - a
带注释代码
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int n,x,q;
int main(){
cin >> n >> q;
// 输入有序数组
for(int i = 1; i <= n; i++) cin >> a[i];
while(q--){
cin >> x;
// lower_bound 找第一个 >= x 的位置
// 返回的是地址，减去 a 之后就是下标
cout << lower_bound(a + 1, a + n + 1, x) - a << endl;
}
}
4. STL upper_bound：第一个 > x
思路简介
upper_bound 的含义是：
找第一个大于 x 的位置
写法：
upper_bound(a + 1, a + n + 1, x)
返回的是地址。
转成下标：
upper_bound(a + 1, a + n + 1, x) - a
带注释代码
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int n,x,q;
int main(){
cin >> n >> q;
// 输入有序数组
for(int i = 1; i <= n; i++) cin >> a[i];
while(q--){
cin >> x;
// upper_bound 找第一个 > x 的位置
// 返回的是地址，减去 a 之后就是下标
cout << upper_bound(a + 1, a + n + 1, x) - a << endl;
}
}
5. 手写 upper_bound：查找第一个 > x 的位置
思路简介
要找的是第一个满足：
a[i] > x
的位置。
二分时，如果：
a[mid] > x
说明 mid 可能是答案，但是前面可能还有更靠左的答案，所以：
ans = mid;
r = mid - 1;
如果：
a[mid] <= x
说明 mid 和左边都不满足，只能往右找：
l = mid + 1;
如果不存在，输出 n + 1。
带注释代码
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int n,x,q;
int main(){
cin >> n >> q;
}
总结口诀
lower_bound：第一个 >= x
upper_bound：第一个 > x
找第一个满足条件的位置：
满足条件时，记录 ans，然后 r = mid - 1
找不到时：
第一个位置类问题，一般输出 n + 1
这几份代码的前提都是：数组必须是有序的。如果题目没保证有序，需要先写：
sort(a + 1, a + n + 1);
出现次数2
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
int q;
cin >> q;
while(q--){
int x,y;
cin >> x >> y;
// 找第一个 >= x 的位置
int l = 1, r = n;
int ans = n + 1;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] >= x){
ans = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
// 找最后一个 <= y 的位置
int l1 = 1, r1 = n;
int ans1 = 0;
while(l1 <= r1){
int mid = (l1 + r1) / 2;
if(a[mid] <= y){
ans1 = mid;
l1 = mid + 1;
}else{
r1 = mid - 1;
}
}
// 如果区间内没有数
if(ans > ans1){
cout << 0 << endl;
}else{
cout << ans1 - ans + 1 << endl;
}
}
return 0;
}
保龄球
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// 结构体：存储每个位置的瓶子数和原始位置编号
struct node {
int c; // 瓶子数
int id; // 原始位置编号，从 1 开始
} a[N];
int n, Q; // n：位置数，Q：查询次数
// 按瓶子数 c 升序排序
bool cmp(node x, node y) {
return x.c < y.c;
}
// 二分查找函数：在有序数组 a 的区间 [l, r] 中查找目标值 x
int BinarySearch(node a[], int l, int r, int x) {
while (l <= r) {
int mid = (l + r) / 2; // 计算中间位置
if (a[mid].c == x) {
return mid; // 找到目标值，返回索引
} else if (a[mid].c > x) {
r = mid - 1; // 目标值在左半区，调整右边界
} else {
l = mid + 1; // 目标值在右半区，调整左边界
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].c;
a[i].id = i;
}
// 按瓶子数升序排序
sort(a + 1, a + n + 1, cmp);
cin >> Q;
while (Q--) {
int m; // 目标瓶子数
cin >> m;
// 二分查找目标值 m 在排序数组中的位置
int pos = BinarySearch(a, 1, n, m);
}
出现次数1
#include<bits/stdc++.h>
using namespace std ;
int a[200010];
int n,x,q;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
cin>>q;
while(q--){
cin>>x;
int r = upper_bound(a+1,a+n+1,x)-a-1;//最后一个>=x的位置
int l = lower_bound(a+1,a+n+1,x)-a; //第一个>=x的位置
cout<<r-l+1<<endl;
}
return 0;
}
和为 0 的 4 个值
// 线索1 A_i+B_j+C_k+D_l == 0
// 线索2 数组长度 n = 1000
// 暴力 循环4次 n^4 = 10^12
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int a[N],b[N],c[N],d[N];
int p[NN],id1 = 0;
int q[NN],id2 = 0;
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i]>>d[i];
//A_i+B_j
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
p[++id1] = a[i]+b[j];
q[id2] = c[i]+d[j];
}
}
sort(q+1,q+id2+1);
long long ans = 0;
for(int i=1;i<=id1;i){
int x = -p[i];
int l = lower_bound(q+1,q+id2+1,x) - a;
int r = upper_bound(q+1,q+id2+1,x) - a;
ans+=r-l;
}
cout<<ans;
return 0;
}
最后一个等于x的元素
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main() {
int n, q, x;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (q--) {
cin >> x;
int ans=-1;
int l = 1,r = n;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]<=x){//找最后一个等于 x位置
if(a[mid]x) ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<ans<<endl;
}
return 0;
}
不同分的人数
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int n,q;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
while(q--){
int x;
cin>>x;
int l = lower_bound(a+1,a+n+1,x)-a;
int r = upper_bound(a+1,a+n+1,x)-a;
cout<<n - (r-l)<<endl;
}
return 0;
}
学生信息查询
#include<bits/stdc++.h>
using namespace std;
struct stu{
string id;
string name;
int sex;
int age;
}a[100010];
bool cmp(stu a,stu b){
return a.id<b.id;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].id>>a[i].name>>a[i].sex>>a[i].age;
sort(a+1,a+n+1,cmp);
int q;
cin>>q;
while(q--){
string t;
cin>>t;
stu x;
x.id = t;
int idx = lower_bound(a+1,a+n+1,x,cmp) - a;
if(a[idx].idt){
cout<<a[idx].id<<" "<<a[idx].name<<" "<<a[idx].sex<<" "<<a[idx].age<<endl;
}else cout<<"No Answer!"<<endl;
}
return 0;
}
A-B数对
// B = A-C
//枚举A 数组中A-C的数量 -> 出现次数
#include<bits/stdc++.h>
using namespace std;
int a[100010],n,C;
int main(){
cin>>n>>C;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
long long ans = 0;
for(int i=1;i<=n;i++){
int B = a[i]-C;
int l = lower_bound(a+1,a+n+1,B)-a;
int r = upper_bound(a+1,a+n+1,B)-a;
ans+=r-l;
}
cout<<ans;
return 0;
}
递增三元组
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
long long a[N], b[N], c[N];
int main(){
int n;
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(c + 1, c + n + 1);
long long ans = 0;
for(int i = 1; i <= n; i++){
// A 中小于 b[i] 的数量
long long x = lower_bound(a + 1, a + n + 1, b[i]) - a - 1;
// C 中大于 b[i] 的数量
long long y = n - (upper_bound(c + 1, c + n + 1, b[i]) - c) + 1;
ans += x * y;
}
cout << ans << '\n';
return 0;
}
放学人潮
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
struct node{
long long x; // 位置
char op; // 方向，'0' 往左，'1' 往右
}a[N];
long long b[N]; // 存所有往右走的人的位置
int cnt = 0;
bool cmp(node a,node b){
return a.x < b.x;
}
int main(){
int n;
long long T;
cin >> n >> T;
string s;
cin >> s;
for(int i = 1;i <= n;i++){
cin >> a[i].x;
a[i].op = s[i - 1];
}
// 按位置从小到大排序
sort(a + 1,a + n + 1,cmp);
// 把所有往右走的学生位置存到静态数组 b 中
for(int i = 1;i <= n;i++){
if(a[i].op == '1'){
b[cnt] = a[i].x;
}
}
long long ans = 0;
// 枚举每一个往左走的人
for(int i = 1;i <= n;i){
if(a[i].op == '0'){
/*
当前人位置为 a[i].x，往左走。
能和他擦肩而过的人必须：
1. 往右走
2. 在他的左边
3. 距离不超过 2*T
}
