2026年7月24日作业题解
2026-07-24 15:54:56
发布于：广东
本题单主要练习二分查找及其常见应用，包括精确查找、边界查找、区间计数、最接近值、前缀和配合二分，以及将四数之和和相遇计数转化为二分统计。
说明：以下代码均使用 C++17。所有数据均使用普通数组保存，不使用
vector、map、set等 STL 容器。可以直接使用sort、lower_bound和upper_bound等算法函数。
普通数组中的 lower_bound 与 upper_bound
假设数组 a 使用从 1 开始的下标，并且已经按非降序排列：
sort(a + 1, a + n + 1);
常用写法如下：
// 第一个大于等于 x 的位置
int p1 = lower_bound(a + 1, a + n + 1, x) - a;
// 第一个大于 x 的位置
int p2 = upper_bound(a + 1, a + n + 1, x) - a;
注意，查找区间写成 [a+1,a+n+1)，其中右端 a+n+1 不属于查找范围。
p1的范围是1到n+1；- 当
p1=n+1时，表示不存在大于等于x的元素； - 当
p2=n+1时，表示不存在大于x的元素。
由此可以得到下面几个常用结论：
// 等于 x 的元素个数
int equalCount = upper_bound(a + 1, a + n + 1, x)
- lower_bound(a + 1, a + n + 1, x);
// 小于 x 的元素个数
int lessCount = lower_bound(a + 1, a + n + 1, x) - (a + 1);
// 大于 x 的元素个数
int greaterCount = (a + n + 1)
- upper_bound(a + 1, a + n + 1, x);
1. 查找 x
题目分析
数组严格递增且元素互不重复，需要查找目标值 x 的位置。因为数组有序，可以使用二分查找。
维护搜索区间 [left,right]：
- 计算中点
mid； - 若
a[mid]==x，直接输出mid； - 若
a[mid]<x，目标值只可能在右半部分； - 若
a[mid]>x，目标值只可能在左半部分； - 搜索区间为空仍未找到时，输出
-1。
正确性说明
每次比较后，都会排除一定不包含 x 的一半区间，同时保留所有可能出现 x 的位置。因此，若 x 存在，最终一定能够找到；若区间为空仍未找到，则数组中不存在 x。
复杂度
- 时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int left = 1, right = n;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == x) {
cout << mid << '\n';
return 0;
}
if (a[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << -1 << '\n';
return 0;
}
2. 查找第一个大于等于目标的数
题目分析
对于每次询问，需要找到第一个满足
的位置，这正是 lower_bound 的作用。
int position = lower_bound(a + 1, a + n + 1, target) - a;
数组下标从 1 开始，所以指针减去数组首地址 a 后，得到的就是题目需要的位置。如果不存在满足条件的元素，lower_bound 会返回 a+n+1，此时 position=n+1，正好符合题意。
正确性说明
lower_bound 返回有序数组中第一个不小于 target 的位置。它前面的元素均小于 target，当前位置满足大于等于 target，因此答案正确。
复杂度
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, Q;
cin >> n >> Q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (Q--) {
int target;
cin >> target;
int position = lower_bound(a + 1, a + n + 1, target) - a;
cout << position << '\n';
}
return 0;
}
3. 查找第一个大于目标的数
题目分析
这道题要求找到第一个严格大于 target 的位置，对应 upper_bound：
int position = upper_bound(a + 1, a + n + 1, target) - a;
如果没有比 target 更大的元素，返回位置就是 n+1。
正确性说明
upper_bound 返回第一个满足 的位置。该位置之前的元素都小于等于 target，所以它就是第一个严格大于目标值的位置。
复杂度
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, Q;
cin >> n >> Q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (Q--) {
int target;
cin >> target;
int position = upper_bound(a + 1, a + n + 1, target) - a;
cout << position << '\n';
}
return 0;
}
4. 出现次数
题目分析
原序列不一定有序，因此先排序。排序后，所有等于 num 的元素会连续排在一起。
lower_bound找到第一个大于等于num的位置；upper_bound找到第一个大于num的位置。
两者之差就是 num 的出现次数：
正确性说明
lower_bound 指向所有 num 的左边界，upper_bound 指向所有 num 的右边界之后。因此两个位置之间恰好包含全部等于 num 的元素。
复杂度
- 排序：
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int m;
cin >> m;
while (m--) {
int num;
cin >> num;
int answer = upper_bound(a + 1, a + n + 1, num)
- lower_bound(a + 1, a + n + 1, num);
cout << answer << '\n';
}
return 0;
}
5. lower_bound：统计小于目标值的数
题目分析
先将序列排序。lower_bound 返回第一个大于等于 num 的位置，因此它前面的元素全部严格小于 num。
答案为：
lower_bound(a + 1, a + n + 1, num) - (a + 1)
这里减去 a+1，得到的是查找位置前面的元素个数。
正确性说明
设 lower_bound 返回位置 p。根据定义，p 前面的所有元素都小于 num，从 p 开始的元素均不小于 num，所以前缀长度就是答案。
复杂度
- 排序：
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int m;
cin >> m;
while (m--) {
int num;
cin >> num;
int answer = lower_bound(a + 1, a + n + 1, num) - (a + 1);
cout << answer << '\n';
}
return 0;
}
6. upper_bound：统计大于目标值的数
题目分析
先将序列排序。upper_bound 返回第一个严格大于 num 的位置，因此从该位置到数组末尾的元素全部大于 num。
答案为：
(a + n + 1) - upper_bound(a + 1, a + n + 1, num)
正确性说明
upper_bound 前面的元素都小于等于 num，从返回位置开始的元素全部严格大于 num，所以后缀长度就是答案。
复杂度
- 排序：
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int m;
cin >> m;
while (m--) {
int num;
cin >> num;
int answer = (a + n + 1)
- upper_bound(a + 1, a + n + 1, num);
cout << answer << '\n';
}
return 0;
}
7. 出现次数 2
题目分析
对于每次询问区间 [l,r]，需要统计满足
的元素数量。
排序后：
lower_bound(l)找到第一个大于等于l的位置；upper_bound(r)找到第一个大于r的位置。
因此答案为：
正确性说明
从 lower_bound(l) 开始，元素都不小于 l；到 upper_bound(r) 之前，元素都不大于 r。两个边界之间恰好是闭区间 [l,r] 内的所有元素。
复杂度
- 排序：
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int m;
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
int answer = upper_bound(a + 1, a + n + 1, r)
- lower_bound(a + 1, a + n + 1, l);
cout << answer << '\n';
}
return 0;
}
8. 保龄球
题目分析
询问给出瓶子数 m，需要输出这个瓶子数在原数组中的位置。原数组不保证有序，但每个位置的瓶子数互不相同。
如果直接排序瓶子数，就会丢失它原来的位置。因此使用结构体同时保存：
bottle：瓶子数；position：原位置。
按瓶子数排序后，再二分查找目标瓶子数。这里使用普通结构体数组，没有使用 STL 容器。
正确性说明
排序只改变记录的排列顺序，不会改变每个瓶子数保存的原位置。二分找到瓶子数 m 后，记录中的 position 就是正确答案；若不存在该瓶子数，则输出 0。
复杂度
- 排序：
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
struct Node {
long long bottle;
int position;
};
Node a[MAXN];
bool cmp(Node x, Node y) {
return x.bottle < y.bottle;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].bottle;
a[i].position = i;
}
sort(a + 1, a + n + 1, cmp);
int Q;
cin >> Q;
while (Q--) {
long long m;
cin >> m;
int left = 1, right = n;
int answer = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid].bottle == m) {
answer = a[mid].position;
break;
}
if (a[mid].bottle < m) {
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << answer << '\n';
}
return 0;
}
9. 和为 0 的 4 个值
题目分析
直接枚举四个下标需要 ，无法通过较大的数据。
将等式
变形为
先枚举所有 C+D，共得到 个和值，并将这些和值排序。随后枚举每一个 A_i+B_j，使用 lower_bound 和 upper_bound 统计 C+D 中有多少个值等于它的相反数。
本题不需要保存 A+B 数组，可以一边枚举 A+B，一边进行二分统计，从而少开一个长度为 的数组。
正确性说明
每组合法四元组都对应一个 A_i+B_j 和一个与它互为相反数的 C_k+D_l。反过来，每找到一对和为零的两数之和，也唯一对应一组合法下标。因此累加所有相反数的出现次数，得到的就是答案。
复杂度
- 枚举
C+D： - 排序：
- 枚举
A+B并二分： - 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 5;
const int MAXSUM = 1000000 + 5;
long long A[MAXN], B[MAXN], C[MAXN], D[MAXN];
long long sumCD[MAXSUM];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
}
int total = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sumCD[total] = C[i] + D[j];
total++;
}
}
sort(sumCD, sumCD + total);
long long answer = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
long long target = -(A[i] + B[j]);
long long count = upper_bound(sumCD, sumCD + total, target)
- lower_bound(sumCD, sumCD + total, target);
answer += count;
}
}
cout << answer << '\n';
return 0;
}
10. 【分治】【二分查找】找数
题目分析
需要找到有序数组中最后一个小于等于 k 的数。
upper_bound(k) 返回第一个严格大于 k 的位置，所以它的前一个位置就是最后一个小于等于 k 的元素：
int position = upper_bound(a + 1, a + n + 1, k) - a - 1;
- 若
position=0，说明所有元素都大于k，输出-1； - 否则输出
a[position]。
正确性说明
upper_bound(k) 之前的元素都小于等于 k，返回位置本身已经严格大于 k，因此它的前一个元素就是最后一个不大于 k 的数。
复杂度
- 时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
long long a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int position = upper_bound(a + 1, a + n + 1, k) - a - 1;
if (position == 0) {
cout << -1 << '\n';
} else {
cout << a[position] << '\n';
}
return 0;
}
11. 查找最接近目标的数
题目分析
原数组不一定有序，先排序。对于目标值 target，使用 lower_bound 找到第一个大于等于它的位置 position。
最接近 target 的元素只可能是：
a[position]，即右侧候选；a[position-1]，即左侧候选。
比较两个候选与目标值的差：
- 差值更小的元素更优；
- 差值相同时，选择数值较小的左侧候选。
还要注意 position=1 和 position=n+1 两种边界情况。
正确性说明
排序后，在所有小于 target 的元素中，最大的那个离目标最近；在所有大于等于 target 的元素中，最小的那个离目标最近。因此只需比较 lower_bound 所在位置及其前一个位置。
复杂度
- 排序：
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
long long a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, Q;
cin >> n >> Q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
while (Q--) {
long long target;
cin >> target;
int position = lower_bound(a + 1, a + n + 1, target) - a;
if (position == 1) {
cout << a[1] << '\n';
} else if (position == n + 1) {
cout << a[n] << '\n';
} else {
long long leftDifference = target - a[position - 1];
long long rightDifference = a[position] - target;
if (leftDifference <= rightDifference) {
cout << a[position - 1] << '\n';
} else {
cout << a[position] << '\n';
}
}
}
return 0;
}
12. 烦恼的高考志愿
题目分析
每名学生都可以独立选择一所分数线最接近的学校，所以总不满意度的最小值，就是每名学生最小不满意度之和。
先将学校分数线排序。对于学生估分 score：
- 使用
lower_bound找到第一个大于等于score的学校位置； - 最接近的学校只可能是这个位置，或者它的前一个位置；
- 取两个分数差中的较小值，加入答案。
答案可能超过 int，需要使用 long long。
正确性说明
排序后，估分左侧最接近的学校一定是小于估分的最大分数线，右侧最接近的学校一定是大于等于估分的最小分数线。因此比较 lower_bound 所在位置和前一个位置即可得到该学生的最小不满意度。每名学生互不影响，分别取最小值再求和即为全局最优答案。
复杂度
- 排序学校分数线：
- 每名学生查询：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
long long school[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> school[i];
}
sort(school + 1, school + m + 1);
long long answer = 0;
for (int i = 1; i <= n; i++) {
long long score;
cin >> score;
int position = lower_bound(school + 1, school + m + 1, score)
- school;
long long best;
if (position == 1) {
best = school[1] - score;
} else if (position == m + 1) {
best = score - school[m];
} else {
long long leftDifference = score - school[position - 1];
long long rightDifference = school[position] - score;
best = min(leftDifference, rightDifference);
}
answer += best;
}
cout << answer << '\n';
return 0;
}
13. 驯鹿和雪橇
题目分析
若想在驯鹿数量有限时拉尽可能多的雪橇，应优先选择需要驯鹿最少的雪橇。
将需求量从小到大排序，并计算前缀和：
对于每次询问 X，需要找到最大的 i，使得
这等价于在前缀和数组中找最后一个小于等于 X 的位置。upper_bound 返回第一个大于 X 的位置，所以答案是返回位置减 1。
正确性说明
在所有选择 k 辆雪橇的方案中，选择需求最小的前 k 辆所需驯鹿最少，总需求为 prefix[k]。
- 若
prefix[k]<=X，就能拉动至少k辆； - 若
prefix[k]>X，其他任意k辆雪橇需要的驯鹿只会更多，因此也无法拉动k辆。
所以最大的满足 prefix[k]<=X 的 k 就是答案。
复杂度
- 排序：
- 前缀和：
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
long long reindeer[MAXN];
long long prefix[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> reindeer[i];
}
sort(reindeer + 1, reindeer + N + 1);
prefix[0] = 0;
for (int i = 1; i <= N; i++) {
prefix[i] = prefix[i - 1] + reindeer[i];
}
while (Q--) {
long long X;
cin >> X;
int answer = upper_bound(prefix, prefix + N + 1, X)
- prefix - 1;
cout << answer << '\n';
}
return 0;
}
14. lower and upper bound
题目分析
对于每个询问 num，需要输出：
- 第一个等于
num的位置； - 最后一个等于
num的位置； - 第一个大于
num的位置。
设：
int left = lower_bound(a + 1, a + n + 1, num) - a;
int right = upper_bound(a + 1, a + n + 1, num) - a;
那么：
- 若
left<=n且a[left]==num，第一个等于的位置是left； - 最后一个等于的位置是
right-1； - 若
right<=n，第一个大于的位置是right； - 不存在对应位置时输出
-1。
正确性说明
lower_bound 是第一个不小于 num 的位置。当该位置的值等于 num 时，它就是第一个等于的位置。upper_bound 是第一个大于 num 的位置，因此它的前一个位置是最后一个等于 num 的位置。
复杂度
- 每次询问：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int m;
cin >> m;
while (m--) {
int num;
cin >> num;
int left = lower_bound(a + 1, a + n + 1, num) - a;
int right = upper_bound(a + 1, a + n + 1, num) - a;
int firstEqual = -1;
int lastEqual = -1;
int firstGreater = -1;
if (left <= n && a[left] == num) {
firstEqual = left;
lastEqual = right - 1;
}
if (right <= n) {
firstGreater = right;
}
cout << firstEqual << ' '
<< lastEqual << ' '
<< firstGreater << '\n';
}
return 0;
}
15. 递增三元组
题目分析
固定中间元素 B[j]，合法三元组的数量为：
分别对数组 A 和 C 排序：
lower_bound(A,B[j])前面的元素个数，就是A中小于B[j]的元素个数；upper_bound(C,B[j])后面的元素个数，就是C中大于B[j]的元素个数。
将两个数量相乘并累加即可。答案最大可能达到 ，必须使用 long long。
正确性说明
固定 B[j] 后，每一个小于它的 A[i] 都可以与每一个大于它的 C[k] 组合，因此合法三元组数量等于两边选择数的乘积。每个三元组都有唯一的中间下标 j，逐个枚举 B[j] 不会遗漏或重复。
复杂度
- 排序：
- 枚举
B并二分： - 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
long long A[MAXN], B[MAXN], C[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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 answer = 0;
for (int i = 1; i <= N; i++) {
long long countA = lower_bound(A + 1, A + N + 1, B[i])
- (A + 1);
long long countC = (C + N + 1)
- upper_bound(C + 1, C + N + 1, B[i]);
answer += countA * countC;
}
cout << answer << '\n';
return 0;
}
16. 放学人潮
题目分析
两名同学只有满足以下条件才会迎面相遇：
- 左边的同学向右走；
- 右边的同学向左走；
- 两人的初始距离不超过
2T。
两人的速度均为每分钟 1 米，相对速度为每分钟 2 米。因此，对于右行同学位置 x_r 和左行同学位置 x_l，相遇条件为
输入中的同学不一定按位置排列，因此使用结构体数组同时保存位置和方向，再按位置排序。
从左向右扫描：
- 遇到向右走的同学，将其位置加入普通数组
rightPosition； - 遇到向左走的同学，之前保存的右行同学都在她左侧；
- 只需统计其中位置不小于
position-2T的同学数量。
因为右行同学的位置按加入顺序递增，可以使用 lower_bound 查找第一个可能相遇的位置。
正确性说明
扫描到一名左行同学时，rightPosition 中恰好保存了她左侧的所有右行同学，方向和相对位置条件已经满足。再通过 lower_bound 排除距离大于 2T 的同学，剩余人数就是会与她相遇的人数。每一对相遇同学只在扫描到其中的左行者时统计一次，因此不会重复。
复杂度
- 排序：
- 每名左行同学二分：
- 总时间复杂度：
- 空间复杂度：
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
struct Student {
long long position;
char direction;
};
Student student[MAXN];
char directionString[MAXN];
long long rightPosition[MAXN];
bool cmp(Student x, Student y) {
return x.position < y.position;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long T;
cin >> N >> T;
cin >> directionString;
for (int i = 1; i <= N; i++) {
cin >> student[i].position;
student[i].direction = directionString[i - 1];
}
sort(student + 1, student + N + 1, cmp);
int rightCount = 0;
long long answer = 0;
long long maxDistance = 2LL * T;
for (int i = 1; i <= N; i++) {
if (student[i].direction == '1') {
rightCount++;
rightPosition[rightCount] = student[i].position;
} else {
long long minimumPosition = student[i].position - maxDistance;
int first = lower_bound(
rightPosition + 1,
rightPosition + rightCount + 1,
minimumPosition
) - rightPosition;
answer += rightCount - first + 1;
}
}
cout << answer << '\n';
return 0;
}
总结
本题单中常见的二分模型可以归纳为：
| 问题类型 | 普通数组写法 |
|---|---|
| 第一个大于等于目标值 | lower_bound(a+1,a+n+1,x)-a |
| 第一个大于目标值 | upper_bound(a+1,a+n+1,x)-a |
| 等于目标值的数量 | upper_bound(...)-lower_bound(...) |
| 小于目标值的数量 | lower_bound(...)-(a+1) |
| 大于目标值的数量 | (a+n+1)-upper_bound(...) |
闭区间 [l,r] 内的数量 |
upper_bound(r)-lower_bound(l) |
| 最后一个小于等于目标值 | upper_bound(...)-a-1 |
| 查找最接近值 | 比较 lower_bound 位置和它的前一个位置 |
| 最大可选数量 | 排序、前缀和、查找最后一个不超过上限的位置 |
学习时最需要注意的不是函数名字，而是下面两点：
- 数组必须已经有序；
- 要分清题目要求的是“大于等于”还是“严格大于”。
这里空空如也
有帮助，赞一个