【题解】Two Contests

把一些线段分成两组,使得 每组线段的并的长度 之和最大……

一 题目

Source

Descriptions

10^9 contestants, numbered 1 to 10^9, will compete in a competition. There will be two contests in this competition.

The organizer prepared N problems, numbered 1 to N, to use in these contests. When Problem i is presented in a contest, it will be solved by all contestants from Contestant Li to Contestant Ri (inclusive), and will not be solved by any other contestants.

The organizer will use these N problems in the two contests. Each problem must be used in exactly one of the contests, and each contest must have at least one problem.

The joyfulness of each contest is the number of contestants who will solve all the problems in the contest. Find the maximum possible total joyfulness of the two contests.

Input

Input is given from Standard Input in the following format:

1
2
3
4
5
N
L1 R1
L2 R2

LN RN

Output

Print the maximum possible total joyfulness of the two contests.


二 题解

首先肯定能想到对线段进行”某种排序“,然后前面分一组,后面分另一组。

然后发现并的长度受两个东西的限制: max(l[i]) 和 min(r[i]) 。
我们先找出所有线段中,l[] 值最大的那一条(记为 p )和 r[] 值最小的那一条(记为 q ),然后分类讨论。

考虑把 p,q 分到同一组线段里,那么显然,这组线段的并的长度一定是 max(0, r[q] - l[p]) 。于是想到留一条最长的线段另成第二组,然后其它的线段都分到第一组里,这样一定是坠吼的。

考虑不把 p,q 分到同一组里,那么考虑通过“某种排序”使得某一组里面的线段在数列里面连续。显然,与 p 分到同一组里面的线段的左端点受制于 p ,也就是说左端点固定,那么我们可以按照右端点进行升序排序,此时答案受制于最小的那个 r[] 值,也就是靠前面的 r[] 值;
再考虑右端点相同的情况,我们可能会把前面一部分线段划给 q ,那么我们需要靠前的线段 l[] 值尽量小,于是按 l[] 升序排序,此时答案受制于最大的那个 l[] 值,也就是靠后面 l[] 值。

剩下的问题是枚举一个断点(前面化成一组,后面另一组),然后贪心就好了。

代码:

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
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;

const int CN = 1e5+5;

int n,l[CN],r[CN],id[CN],mnr,pr,mxl,pl;
long long ans = 0;

/* calc the length of a certain segment */
long long d(int cl,int cr) {return 1ll * max(0, cr - cl + 1);}

bool cmp(int x,int y){
return r[x] != r[y] ? r[x] < r[y] : l[x] < l[y];
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);

mnr = 0x7f7f7f7f;
for(int i=1;i<=n;i++) if(r[i] < mnr) mnr = r[pr = i];
mxl = 0;
for(int i=1;i<=n;i++) if(l[i] > mxl) mxl = l[pl = i];

/* in same */
for(int i=1;i<=n;i++)
if(i != pl && i != pr)
ans = max(ans, d(mxl, mnr) + d(l[i], r[i]));

/* in diff */
for(int i=1;i<=n;i++) id[i] = i;
sort(id + 1, id + n + 1, cmp);
int premxl = 0;
for(int i=2;i<=n;i++){
premxl = max(premxl, l[ id[i - 1] ]);
ans = max(ans, d(mxl, r[ id[i] ]) + d(premxl, mnr));
}

printf("%lld",ans);

return 0;
}

$$ - - - - \mathcal{End} - - - - $$


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×