二分算法实战宝典：洛谷三大经典题目C++与Python双解

#include <bits/stdc++.h>
using namespace std;
int a[1000005], n, m;

int search(int x) {
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (a[mid] >= x) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return a[ans] == x ? ans : -1;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    while (m--) {
        int q; scanf("%d", &q);
        printf("%d ", search(q));
    }
    return 0;
}

Python版（递归优化）

def search(nums, target):
    left, right, res = 0, len(nums)-1, -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            res = mid
            right = mid - 1
        else:
            left = mid + 1
    return res + 1 if res != -1 and nums[res] == target else -1

n, m = map(int, input().split())
nums = list(map(int, input().split()))
queries = list(map(int, input().split()))
print(' '.join(str(search(nums, q)) for q in queries))

📌 题目二：P1102 A-B 数对

题目描述

求数组中满足A - B = C的数对总数，不同位置的相同数值视为不同数对。
输入样例：

4 1
1 1 2 3

输出样例：

解题思路

方法一（哈希表）：统计每个数的出现次数，遍历时累加num + C的出现次数
方法二（双指针）：排序后固定B，用双指针快速定位A的范围

代码实现

C++版（哈希表法，时间复杂度：O(n)）

#include <bits/stdc++.h>
using namespace std;
unordered_map<long, long> cnt;

int main() {
    int n, c; 
    long ans = 0;
    cin >> n >> c;
    vector<long> nums(n);
    for (auto &num : nums) {
        cin >> num;
        cnt[num]++;
    }
    for (auto num : nums) ans += cnt[num + c];
    cout << ans;
    return 0;
}

Python版（双指针法，时间复杂度：O(n logn)）

n, c = map(int, input().split())
nums = sorted(list(map(int, input().split())))
ans, j = 0, 0

for i in range(n):
    while j < n and nums[j] - nums[i] < c:
        j += 1
    start = j
    while j < n and nums[j] - nums[i] == c:
        ans += 1
        j += 1
    j = start  # 重置指针避免重复计数
print(ans)

📌 题目三：P1873 砍树

题目描述

确定伐木机的最大高度H，使得砍下的木材总长度≥M。
输入样例：

4 7
20 15 10 17

输出样例：

解题思路

二分答案：在[0, max(tree_heights)]区间内二分H，计算当前H下的木材总量
单调性：H越大，木材总量越小，满足二分条件

代码实现

C++版（二分答案模板）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, trees[1000005];

ll calc(ll h) {
    ll sum = 0;
    for (ll i = 0; i < n; i++) 
        if (trees[i] > h) sum += trees[i] - h;
    return sum;
}

int main() {
    cin >> n >> m;
    ll l = 0, r = 0;
    for (ll i = 0; i < n; i++) {
        cin >> trees[i];
        r = max(r, trees[i]);
    }
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (calc(mid) >= m) l = mid + 1;
        else r = mid - 1;
    }
    cout << r;
    return 0;
}

Python版（递归优化）

def max_height():
    n, m = map(int, input().split())
    trees = list(map(int, input().split()))
    left, right = 0, max(trees)
    
    def check(h):
        return sum(t - h for t in trees if t > h) >= m
    
    while left <= right:
        mid = (left + right) // 2
        if check(mid): left = mid + 1
        else: right = mid - 1
    return right

print(max_height())