题目描述
三个农民每天清晨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 <cstdio>
#include <string>
#include <cstring>
#include <iostream> using namespace std; class T_tree {
public:
int l,r,mid; bool flag,dis; void flag_()
{
flag=true;
} void mid_()
{
mid=(l+r)>>;
} bool if_()
{
if(l==r) return true;
else return false;
}
};
class T_tree tree[*]; int n,maxn,do_l[],do_r[],cnt=; char Cget; bool result[]; inline void read_int(int &now_)
{
Cget=getchar();
while(Cget>''||Cget<'') Cget=getchar();
while(Cget<=''&&Cget>='')
{
now_=now_*+Cget-'';
Cget=getchar();
}
} void tree_build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r;
if(l==r)
{
tree[now].dis=true;
return ;
}
tree[now].mid_();
tree_build(now<<,l,tree[now].mid);
tree_build(now<<|,tree[now].mid+,r);
} inline void tree_down(int now)
{
if(tree[now].l==tree[now].r) return ;
tree[now<<].flag_();
tree[now<<].dis=false;
tree[now<<|].flag_();
tree[now<<|].dis=false;
} void tree_change(int now,int l,int r)
{
if(tree[now].l==l&&tree[now].r==r)
{
tree[now].dis=false;
tree[now].flag_();
return ;
}
if(tree[now].flag) tree_down(now);
if(r<=tree[now].mid) tree_change(now<<,l,r);
else if(l>tree[now].mid) tree_change(now<<|,l,r);
else
{
tree_change(now<<,l,tree[now].mid);
tree_change(now<<|,tree[now].mid+,r);
}
} void tree_result(int now)
{
if(tree[now].if_())
{
result[++cnt]=tree[now].dis;
return ;
}
if(tree[now].flag) tree_down(now);
tree_result(now<<);
tree_result(now<<|);
} int main()
{
read_int(n);
for(int i=;i<=n;i++)
{
read_int(do_l[i]);
read_int(do_r[i]);
maxn=max(maxn,do_r[i]);
}
tree_build(,,maxn);
for(int i=;i<=n;i++)
{
tree_change(,do_l[i]+,do_r[i]);
}
tree_result();
int max_t=,max_f=,max_tt;
for(int i=;i<=cnt;i++)
{
if(!result[i])
{
max_tt=;
for(int j=i+;j<=cnt;j++)
{
if(result[j]==result[j-]) max_tt++;
else
{
if(result[j-]) max_t=max(max_t,max_tt);
else max_f=max(max_f,max_tt);
max_tt=;
}
}
if(result[cnt]) max_t=max(max_t,max_tt);
else max_f=max(max_f,max_tt);
break;
}
}
printf("%d %d\n",max_f,max_t);
return ;
}