题目描述
三个农民每天清晨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：
3
300 1000
700 1200
1500 2100
输出样例#1：
900 300
说明
题目翻译来自NOCOW。
USACO Training Section 1.2
题解：前缀和打标记模拟
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,x,y,l,r,ans_youren,ans_wuren,youren,wuren;
int sum[];
int main(){
scanf("%d",&n);
l=0x7fffffff;r=-;
ans_youren=ans_wuren=-;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
l=min(l,x);
r=max(r,y);
sum[x]++;sum[y]--;
}
for(int i=l;i<=r;i++)sum[i]+=sum[i-];
for(int i=l;i<=r;i++){
if(sum[i]){
ans_wuren=max(ans_wuren,wuren);
wuren=;
youren++;
}else{
ans_youren=max(ans_youren,youren);
youren=;
wuren++;
}
}
cout<<ans_youren<<" "<<ans_wuren<<endl;
return ;
}
另一种做法，洛谷的标签是线段树，题解中有个用线段树离散化做的，把每一个时间段看成一个点，
点值为时间长短，把空闲时间的点值看做负数，最后求最大值和最小值的负数即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; #define maxn 5009
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r int n,z[maxn]; struct T{
int l,r;
bool operator < (const T &a)const {
return l<a.l;
}
}t[maxn]; struct Tree{
int minl,maxl;
}tr[maxn<<]; void update(int rt){
tr[rt].minl=min(tr[rt<<].minl,tr[rt<<|].minl);
tr[rt].maxl=max(tr[rt<<].maxl,tr[rt<<|].maxl);
} void build(int rt,int l,int r){
if(l==r){
tr[rt].minl=min(,z[l]);
tr[rt].maxl=z[l];
return;
}
int mid=(l+r)>>;
build(lson);build(rson);
update(rt);
return;
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d",&t[i].l,&t[i].r);
sort(t+,t+n+);
int p=,ll=t[].l,rr=t[].r;
for(int i=;i<=n;i++){
if(t[i].l>=ll&&t[i].r<=rr)continue;
if(t[i].l<=rr&&t[i].r>rr)rr=t[i].r;
else {
z[++p]=rr-ll;
z[++p]=-(t[i].l-rr);
ll=t[i].l;rr=t[i].r;
}
}
z[++p]=rr-ll;
build(,,p);
printf("%d %d",tr[].maxl,-tr[].minl);
return ;
}