题目描述

三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

你的任务是编一个程序,读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表,计算以下两点(均以秒为单位):

最长至少有一人在挤奶的时间段。

最长的无人挤奶的时间段。(从有人挤奶开始算起)

输入输出格式

输入格式:

Line 1:

一个整数N。

Lines 2..N+1:

每行两个小于1000000的非负整数,表示一个农民的开始时刻与结束时刻。

输出格式:

一行,两个整数,即题目所要求的两个答案。

输入输出样例

输入样例#1:

1
2
3
4
3
300 1000
700 1200
1500 2100

输出样例#1:

1
900 300

解法

USA Cow Olympiad的题目真是优质…

开始想到拿一个桶模拟,但是数据范围太大,于是拿线段树来做。

我们把每个时间段转化成一个点,每个点的值即为长度。我们把有人挤奶的时间段记为正数,无人挤奶的时间段记为负数,问题就转化为了求解区间最大值与区间最小值。

将每个时间段按照左端点排序存储到线段树中,只需要建树即可,最后的答案为所有点的最大值与所有点的最小值。

注意给最小值赋初值的时候要与0取一遍最小值,否则只有1个时间段的时候最小值就会变为正数,影响到解法的正确性。

细节不少,详情请见代码。

代码

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn=5050;
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int minn[maxn<<2],maxx[maxn<<2],z[maxn<<2];
int n;
struct tim {
int l,r;
}t[maxn];
bool cmp(tim p,tim q) {
return p.l<q.l;
}
inline void pushup(int rt) {
minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
}
inline void build(int rt,int l,int r) {
if(l==r) {
minn[rt]=min(0,z[l]);
maxx[rt]=z[l];
return ;
}
build(lson);build(rson);pushup(rt);
}
int cnt;
int main() {
cin>>n;
for(int i=1;i<=n;i++) cin>>t[i].l>>t[i].r;
sort(t+1,t+n+1,cmp);
int L=t[1].l;
int R=t[1].r;
for(int i=1;i<=n;i++) {
if(t[i].l<=R && t[i].r>R) R=t[i].r;
else if(t[i].r<=R && t[i].l>L) continue;
else {
z[++cnt]=R-L;
z[++cnt]=-(t[i].l-R);
L=t[i].l;R=t[i].r;
}
}
z[++cnt]=R-L;
build(1,1,cnt);
cout<<maxx[1]<<' '<<-minn[1]<<endl;
return 0;
}