未命名
例题
例题 1：Counting Haybales
给定 N 个不同位置的干草捆，有 Q 次查询，每次查询区间 [A, B] 内有多少个干草捆。
- N, Q ≤ 100,000
- 坐标范围：0 ~ 1,000,000,000
思路：
- 先将所有干草捆位置排序
- 对于每次查询 [A, B]：
<= B的个数：upper_bound(B)<= A-1的个数：upper_bound(A-1)- 答案 =
upper_bound(B) - upper_bound(A-1)
import sys
from bisect import bisect_right
sys.stdin = open("haybales.in", "r")
sys.stdout = open("haybales.out", "w")
N, Q = map(int, input().split())
arr = sorted(list(map(int, input().split())))
for _ in range(Q):
a, b = map(int, input().split())
print(bisect_right(arr, b) - bisect_right(arr, a - 1))复杂度：O(N log N + Q log N)
例题 2：最大中位数（单调函数 + max_ok）
来源：Codeforces - Maximum Median
给定 n 个整数的数组（n 为奇数），可以进行 k 次操作（每次+1），求最大可达中位数。
1 ≤ n ≤ 2 × 10^5，1 ≤ k ≤ 10^9
思路：
排序数组：先对数组进行升序排序
观察：要将中位数提升到 x，需要将所有大于等于当前中位数的元素都提升到至少 x
例如，对于排序后的数组
[1,1,2,3,4,4,5,5,6,8,8]，当前中位数是 4，要将中位数提升到 6，需要：- 将 4 → 6（2 次操作）
- 将 5 → 6（1 次操作 × 2 个）
- 将 6,8,8 保持不变
单调性：将中位数提升到 x 所需的操作数随着 x 增加而单调递增
二分搜索：使用
max_ok找到最大的 x 使得所需操作数 ≤ k
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]
arr.sort()
def max_ok(lo, hi, check):
lo -= 1
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if check(mid):
lo = mid
else:
hi = mid - 1
return lo
def med_reachable(x):
ops = 0
for i in range((n - 1) // 2, n):
ops += max(0, x - arr[i])
return ops <= k
ans = max_ok(1, int(2e9), med_reachable)
print(ans)例题 3：Cow Dance Show（min_ok + 堆模拟）
有 N 头牛按顺序表演，每头牛舞蹈时长为 d(i)。舞台能容纳 K 头牛同时表演。初始时前 K 头牛上台，当其中任何一头牛完成表演后，立即由下一头牛补上（直到所有牛表演完）。求在演出时间不超过 Tmax 的前提下，最小的 K 是多少。
1 ≤ N ≤ 10,000，Tmax ≤ 10^6，1 ≤ d(i) ≤ 100,000
思路：
单调性：K 越大，演出时间 T 越小
- 如果 K 可以让演出在 Tmax 内完成，那么 K+1、K+2 也可以
- 单调递增：随着 K 增大，T 单调递减
二分搜索：使用
min_ok找到最小的可行 K模拟演出：使用小顶堆模拟 K 个同时在舞台上的牛
- 每次取出最早结束的牛，用下一头牛替换
- 最终演出时间 = 堆中所有牛完成时间的最大值
import sys
import heapq
sys.stdin = open("cowdance.in", "r")
sys.stdout = open("cowdance.out", "w")
n, t = map(int, input().split())
d = [int(input()) for _ in range(n)]
def fun(k):
"""模拟舞台大小为 k 时的演出时间"""
show = d[:k]
heapq.heapify(show)
for i in range(k, n):
earliest = heapq.heappop(show) # 最早结束的牛
heapq.heappush(show, earliest + d[i]) # 下一头牛上台
return max(show) # 最终演出时间
def min_ok(lo, hi, check):
"""查找最小的 x 使得 check(x) = True"""
hi += 1
while lo < hi:
mid = lo + (hi - lo) // 2
if check(mid):
hi = mid
else:
lo = mid + 1
return lo
print(min_ok(1, n, lambda k: fun(k) <= t))关键点：
- 搜索范围：
[1, N]（最多 N 头牛同时上台） - 单调性：K 越大 T 越小 → 使用
min_ok找最小可行 K - 堆的作用：O(N log K) 时间模拟演出过程
例题 4：Convention 机场接机（min_ok + 贪心验证）
有 N 头奶牛到达机场，时间为 t1…tN。有 M 辆大巴，每辆可乘 C 头奶牛。大巴发车时间 = 最后一头乘坐该大巴的奶牛的到达时间。求最大等待时间（发车时间 - 到达时间）的最小值。
N, M ≤ 10^5，C ≤ N，ti ≤ 10^9
思路：
排序：将奶牛到达时间按升序排列
问题转化：不直接问”能否用 M 辆大巴在等待时间 X 内完成”，而是问”在等待时间 X 内最少需要多少辆大巴”
单调性：
- 如果在等待时间 X 下无法完成，那么更小的 X 也不可能完成
- 随着 X 增大，所需大巴数单调递减
验证函数的三种情况（处理每头牛）：
- 添加这头牛会导致第一头牛超过最大等待时间 → 开新大巴
- 添加这头牛会导致大巴超载 → 开新大巴
- 可以加入当前大巴 → 直接加入
二分搜索：使用
min_ok找到最小的可行 X
def can_arrange(x):
"""检查是否能在最大等待时间 x 内用 M 辆大巴接完所有奶牛"""
need_bus = 1 # 第一辆大巴
first_ind = 0 # 当前大巴上第一头牛的索引
cow_up = 1 # 当前大巴上的牛数量
for i in range(1, n):
# 等待时间超限或容量满，新开大巴
if time[i] - time[first_ind] > x or cow_up == c:
first_ind = i
need_bus += 1
cow_up = 1
else:
cow_up += 1
return need_bus <= m
def min_ok(lo, hi, check):
"""查找最小的 x 使得 check(x) = True"""
hi += 1
while lo < hi:
mid = lo + (hi - lo) // 2
if check(mid):
hi = mid
else:
lo = mid + 1
return lo
n, m, c = map(int, input().split())
time = sorted([int(x) for x in input().split()])
ans = min_ok(0, time[-1] - time[0], can_arrange)
print(ans)关键点：
- 搜索范围：
[0, max_time - min_time] - 单调性：X 越大，所需大巴数越少 → 使用
min_ok - 复杂度：O(N log N)