2024蓝桥杯省赛保奖突击班-Day1-二分查找_笔记

本文主要是介绍2024蓝桥杯省赛保奖突击班-Day1-二分查找_笔记_练习题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3月22日-课堂笔记

非降序序列二分查找等于 $x$ 的数下标

int find(int x, int l, int r) {while(l < r) {int mid = (l + r) / 2;if(x <= a[mid]) r = mid;else l = mid + 1;}return l;
}

非降序可重序列下标最小 $\geq x$ 的元素

int find(int x, int l, int r) {while(l < r) {int mid = (l + r) / 2;if(a[mid] >= x) r = mid;else l = mid + 1;}return l;
}

C++ STL 的使用

vector<int> a(n);
int id = lower_bound(a.begin(), a.end(), x) - a.begin();
int id = upper_bound(a.begin(), a.end(), x) - a.begin();
int a[N];
int id = lower_bound(a + 1, a + n + 1, x) - a;
int id = upper_bound(a + 1, a + n + 1, x) - a;

a中元素 $x$ 出现的次数 $\mathcal{O}(\log n)$

int count = upper_bound(a.begin(),a.end(),x) – lower_bound(a.begin(),a.end(),x);

练习题解

P1102 A-B 数对

题目链接：P1102

参考思路

对于给定的 $A - B = C$ ，其中 $C$ 已知，那么我们可以枚举 $A$ 二分查找 $B$ 的范围，其中

C++参考代码

//用系统库函数
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL);int n, C;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 L = lower_bound(a + 1, a + n + 1, a[i] - C) - a;int R = upper_bound(a + 1, a + n + 1, a[i] - C) - a - 1;ans += R - L + 1;}cout << ans << endl;return 0;
}

//方便大家理解手动实现了一下函数
#include <bits/stdc++.h>using namespace std;int lowerBound(const vector<int>& a, int key) {int low = 0, high = a.size();while (low < high) {int mid = (low + high) / 2;if (a[mid] < key) {low = mid + 1;} else {high = mid;}}return low;
}int upperBound(const vector<int>& a, int key) {int low = 0, high = a.size();while (low < high) {int mid = (low + high) / 2;if (a[mid] <= key) {low = mid + 1;} else {high = mid;}}return low;
}int main() {int n, C;cin >> n >> C;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}sort(a.begin(), a.end());long long ans = 0;for (int i = 0; i < n; ++i) {int L = lowerBound(a, a[i] - C);int R = upperBound(a, a[i] - C);ans += R - L;}cout << ans << endl;return 0;
}

Java参考代码

import java.util.*;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n, C;n = scanner.nextInt();C = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; ++i) {a[i] = scanner.nextInt();}Arrays.sort(a);long ans = 0;for (int i = 0; i < n; ++i) {int L = lowerBound(a, a[i] - C);int R = upperBound(a, a[i] - C);ans += R - L;}System.out.println(ans);scanner.close();}static int lowerBound(int[] a, int key) {int low = 0;int high = a.length;while (low < high) {int mid = (low + high) / 2;if (a[mid] < key) {low = mid + 1;} else {high = mid;}}return low;}static int upperBound(int[] a, int key) {int low = 0;int high = a.length;while (low < high) {int mid = (low + high) / 2;if (a[mid] <= key) {low = mid + 1;} else {high = mid;}}return low;}
}

Python参考代码

def lower_bound(a, key):low, high = 0, len(a)while low < high:mid = (low + high) // 2if a[mid] < key:low = mid + 1else:high = midreturn lowdef upper_bound(a, key):low, high = 0, len(a)while low < high:mid = (low + high) // 2if a[mid] <= key:low = mid + 1else:high = midreturn lowdef main():n, C = map(int, input().split())a = list(map(int, input().split()))a.sort()ans = 0for i in range(n):L = lower_bound(a, a[i] - C)R = upper_bound(a, a[i] - C)ans += R - Lprint(ans)if __name__ == "__main__":main()

P1678 烦恼的高考志愿

题目链接：P1678

参考思路

题目意思其实就是求某一个学生和某一个分数线最小的差的绝对值，求和。
那么我们先对学校分数线 $a$ 数组排序，然后对于每一个学生 $b_i$ 去学校分数也就是 $a$ 数组中二分查找学生分数 $b_i$ 左右两边最近的数即：最后一个小于等于 $b_i$ 的数和第一个大于等于 $b_i$ 的数。
特别注意特殊处理当所有的分数都高于或者低于学生分数的情况。

C++参考代码

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int findr(int t, int l, int r) {while (l < r) {int mid = (l + r) / 2;if (t <= a[mid]) {r = mid;} else {l = mid + 1;}}return l;
}int findl(int t,int l, int r) {while (l < r) {int mid = (l + r + 1) / 2;if (t >= a[mid]) {l = mid;} else {r = mid - 1;}}return l;
}
int main() {int m, n;cin >> m >> n;for (int i = 0; i < m; i++)cin >> a[i];for (int i = 0; i < n; i++)cin >> b[i];sort(a, a + m);long long res = 0;for (int i = 0; i < n; i++) {if (b[i] <= a[0])res += abs(b[i] - a[0]);else if (b[i] >= a[m - 1])res += abs(b[i] - a[m - 1]);else {int l = a[findr(b[i], 0, m)];int r = a[findl(b[i], 0, m)];int ls = abs(l - b[i]);int rs = abs(r - b[i]);if (ls < rs) {res += ls;} else {res += rs;}}}cout << res << endl;return 0;
}

Java参考代码

import java.util.*;public class Main {static int[] a = new int[100010];static int[] b = new int[100010];static int findr(int t, int l, int r) {while (l < r) {int mid = (l + r) / 2;if (t <= a[mid]) {r = mid;} else {l = mid + 1;}}return l;}static int findl(int t, int l, int r) {while (l < r) {int mid = (l + r + 1) / 2;if (t >= a[mid]) {l = mid;} else {r = mid - 1;}}return l;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();for (int i = 0; i < m; i++)a[i] = scanner.nextInt();for (int i = 0; i < n; i++)b[i] = scanner.nextInt();Arrays.sort(a, 0, m);long res = 0;for (int i = 0; i < n; i++) {if (b[i] <= a[0])res += Math.abs(b[i] - a[0]);else if (b[i] >= a[m - 1])res += Math.abs(b[i] - a[m - 1]);else {int l = a[findr(b[i], 0, m)];int r = a[findl(b[i], 0, m - 1)];int ls = Math.abs(l - b[i]);int rs = Math.abs(r - b[i]);if (ls < rs) {res += ls;} else {res += rs;}}}System.out.println(res);}
}

Python参考代码

def findr(t, l, r):while l < r:mid = (l + r) // 2if t <= a[mid]:r = midelse:l = mid + 1return ldef findl(t, l, r):while l < r:mid = (l + r + 1) // 2if t >= a[mid]:l = midelse:r = mid - 1return lm, n = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))a.sort()res = 0
for i in range(n):if b[i] <= a[0]:res += abs(b[i] - a[0])elif b[i] >= a[m - 1]:res += abs(b[i] - a[m - 1])else:l = a[findr(b[i], 0, m)]r = a[findl(b[i], 0, m - 1)]ls = abs(l - b[i])rs = abs(r - b[i])if ls < rs:res += lselse:res += rsprint(res)