题目：
现在有 𝑛 个位置 1…𝑛 。
给𝑞个区间，请你选出选𝑞−2个，使得覆盖位置个数最大。
输入
第一行两个数n,q(3<=n,q<=5000)。
接下来q行，其中第i行两个数l[i],r[i]，表示第i个区间能覆盖所有满足l[i]<=x<=r[i]的位置x。
输出
一个数表示最大值。
输入样例
输出样例
题解：
暴力即可
代码：
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
struct point{
int l,r;
};
point p[5010];
int sum[5010];
int main()
{
int n,q;
scanf("%d%d", &n, &q);
for(int i = 0; i < q; i++)
scanf("%d%d", &p[i].l, &p[i].r);
int now = 0;
for(int i = 0; i < q; i++)
for(int j = p[i].l; j <= p[i].r; j++){
if(sum[j] == 0)
now++;
sum[j]++;
}
int MIN = 99999;
int o = 0;
for(int i = 0; i < q; i++){
int s = 0;
for(int j = p[i].l; j <= p[i].r; j++){
sum[j]--;
if(sum[j] == 0)
s++;
}
if(s < MIN)
o = i;
MIN = min(MIN,s);
for(int j = p[i].l; j <= p[i].r; j++){
sum[j]++;
}
}
now -= MIN;
MIN = 9999;
for(int i = p[o].l; i <= p[o].r; i++)
sum[i]--;
for(int i = 0; i < q; i++){
if(i == o)
continue;
int s = 0;
for(int j = p[i].l; j <= p[i].r; j++){
sum[j]--;
if(sum[j] == 0)
s++;
}
MIN = min(MIN,s);
for(int j = p[i].l; j <= p[i].r; j++){
sum[j]++;
}
}
printf("%d", now - MIN);
return 0;
}
|