1. 服务大厅
有 $n$ 位市民在服务大厅门口有序排队办理业务,其中第 $i$ 位市民办理业务所需时间为 $t_i$,当服务大厅开放 $m$ 个服务窗口时,表示能同时办理 $m$ 位市民的业务。由于每位市民所办理业务的时间不同,办理完成的市民离开窗口时,当前在等待队列中的第一个市民会前往该窗口继续办理业务。
因服务大厅 $T$ 分钟后将关闭,请你帮志愿者小爱计算一下,最少需要开放多少个服务窗口,才能使最后办完业务的市民离开服务大厅时间不超过 $T$?
限制:
- $1 \leqslant n \leqslant 2 \times 10^4$
- $1 \leqslant T \leqslant 10^6$
算法分析
假设最少需要 $x$ 个服务窗口,则多于 $x$ 个服务窗口显然可以在时间 $T$ 内办完业务,而少于 $x$ 个服务窗口就不能在时间 $T$ 内办完业务,满足二段性,所以可以对 $x$ 进行二分。
那么 check
函数怎么写?
先按顺序占满每个服务窗口,然后哪个服务窗口的先办完后面的人就过去办理,在所有人办理结束后,每个窗口的总的办理时间的最大值应该要不超过 $T$
可以用小根堆来维护
弱化题: 使结果不超过阈值的最小除数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> t(n);
rep(i, n) cin >> t[i];
int T;
cin >> T;
int wa = 0, ac = 1e6+5;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
auto ok = [&]{
priority_queue<int, vector<int>, greater<int>> q;
rep(i, n) {
if (q.size() == wj) {
int v = q.top(); q.pop();
q.push(v+t[i]);
}
else {
q.push(t[i]);
}
}
int res = 0;
while (q.size()) {
res = max(res, q.top());
q.pop();
}
return res <= T;
}();
if (ok) ac = wj; else wa = wj;
}
cout << ac << '\n';
return 0;
}
2. 区间交集(二)
给定 $n$ 个数轴上的闭区间 $[a_i, b_i]$,请统计有多少对区间的交集不是空集。
限制:
- $1 \leqslant n \leqslant 3 \times 10^5$
- $1 \leqslant a_i \leqslant b_i \leqslant n$
算法分析
这种统计有多少对满足题意,首先想下暴力
$O(n^2)$ 复杂度
正解:
判断区间是否有交集,其实比较麻烦,怎么简单判断?
- 如果已知左端点的大小顺序,那么判断是否有交集会很简单
- 由此可以得到一个思路,即对所有区间按照左端点从小到大排序,那么我们对于第 $i$ 个区间考虑第 $i+1 \sim n$ 个区间,这些区间的左端点都比第 $i$ 个区间的左端点大,那么只需判断右端点 $y$ 和这些左端点的关系(二分)
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
struct Interval {
int l, r;
Interval() {}
Interval(int l, int r): l(l), r(r) {}
bool operator<(const Interval& o) const {
return l < o.l;
}
};
inline int read() {
int x = 0;
char c;
while (c < '0' or c > '9') c = getchar();
while ('0' <= c and c <= '9') {
x = x*10+c-'0';
c = getchar();
}
return x;
}
int main() {
int n = read();
vector<Interval> intervals(n);
rep(i, n) {
intervals[i].l = read();
intervals[i].r = read();
}
sort(intervals.begin(), intervals.end());
ll ans = 0;
rep(i, n) {
// 每次找出有多少个 j>i 满足第 j 个区间和第 i 个区间相交 (intervals[j].l <= intervals[i].r)
int ac = i, wa = n;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
if (intervals[wj].l <= intervals[i].r) ac = wj; else wa = wj;
}
ans += ac-i;
}
cout << ans << '\n';
return 0;
}
3. 均匀分段
给定 $n$ 个整数 $a_1,a_2,\cdots, a_n$ ,请将它们分割成 $m$ 段(每一段都应该是原序列中连续的一段),使得这些片段的和的最大值最小。
限制:
- $1 \leqslant n \leqslant 2 \times 10^5$
- $1 \leqslant m \leqslant n$
- $1 \leqslant a_i \leqslant 10000$
算法分析
首先我们弱化一下题目(但是不会改变结论):将题目中的“分割为 $m$ 段”改为“至多分割为 $m$ 段”。
这样做的好处是,如果我们询问“能否把原数组分成至多 $m$ 段,使得每一段的和小于等于 $x$ ”会比“能否把原数组分成恰好 $m$ 段,使得每一段的和小于等于 $x$”更容易处理。
如果我们用 check(x)
函数的结果表示“能否把原数组分成至多 $m$ 段,使得每一段的和小于等于 $x$”的结果,则它是具有很好的二分的性质的:如果 check(x)
为 true
,则对于所有 $y \geqslant x$,check(y)
也为 true
。所以我们只需要使用二分的方式找到最小的 $x$,使得 check(x)
为 true
,则它即为本题的结果。
双倍经验:分割数组的最大值
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
rep(i, n) cin >> a[i];
int wa = 0, ac = 2e9+5;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
auto ok = [&]{
int sum = 0, cnt = 0;
rep(i, n) {
if (a[i] > wj) return false;
if (sum+a[i] > wj) {
sum = a[i];
cnt++;
}
else sum += a[i];
}
if (sum) cnt++;
return cnt <= m;
}();
if (ok) ac = wj; else wa = wj;
}
cout << ac << '\n';
return 0;
}
4. 找出第 K 小的数对距离
假设答案为 $x$
找到所有距离不超过 $x$ 的数对数量 cnt
,且满足 $cnt \geqslant k$ 的 $x$ 的最小值
C++ 代码
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int wa = -1, ac = 1e6+5;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
auto ok = [&]{
int cnt = 0;
for (int i = 0, j = 0; j < nums.size(); ++j) {
while (nums[j] - nums[i] > wj) i++;
cnt += j-i;
}
return cnt >= k;
}();
if (ok) ac = wj; else wa = wj;
}
return ac;
}
};