题目链接：Codeforces 1132C
首先预处理所有的询问，统计每个段有多少个人涂，即对每个\([l_i, r_i]\)区间加一。
我们需要\(q-2\)个人，反向考虑我们删掉哪两个。枚举删掉的第一个，把他的区间贡献从预处理的数组中删去，然后用一个新的数组\(c\)来记录哪些点只有一个人涂，即\(c_i = [a_i = 1]\)。接着我们去枚举除了第一个人之外的所有人，如果把他们删掉，那么会有多少个点变成0，即对\(c_i\)求前缀和，这个值为\(pre[r_i] - pre[l_i - 1]\)。我们希望这个值尽可能的小，因此最小的那个就是我们要删除的第二个点。
这种固定一个（枚举），求另一个的方法是一种常用方法。
时间复杂度\(O(nq + q^2)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 5000 + 5;
int n, q, ans, l[MAX_N], r[MAX_N], itv[MAX_N], c[MAX_N];
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= q; ++i) scanf("%d%d", l + i, r + i);
for (int i = 1; i <= q; ++i) {
for (int j = l[i]; j <= r[i]; ++j) {
++itv[j];
}
}
for (int i = 1; i <= q; ++i) {
for (int j = l[i]; j <= r[i]; ++j) --itv[j];
int sum = 0;
for (int j = 1; j <= n; ++j) {
c[j] = (itv[j] == 1) + c[j - 1];
sum += (itv[j] > 0);
}
int minWork = INT_MAX;
for (int j = 1; j <= q; ++j) {
if (i == j) continue;
minWork = min(minWork, c[r[j]] - c[l[j] - 1]);
}
ans = max(sum - minWork, ans);
for (int j = l[i]; j <= r[i]; ++j) ++itv[j];
}
printf("%d\n", ans);
return 0;
}
|