首页 > 代码库 > AC日记——挤牛奶 洛谷 P1204
AC日记——挤牛奶 洛谷 P1204
题目描述
三个农民每天清晨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：
3300 1000700 12001500 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)>>1; } bool if_() { if(l==r) return true; else return false; }};class T_tree tree[1000001*4];int n,maxn,do_l[5001],do_r[5001],cnt=0;char Cget;bool result[1000001];inline void read_int(int &now_){ Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget<=‘9‘&&Cget>=‘0‘) { now_=now_*10+Cget-‘0‘; 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<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r);}inline void tree_down(int now){ if(tree[now].l==tree[now].r) return ; tree[now<<1].flag_(); tree[now<<1].dis=false; tree[now<<1|1].flag_(); tree[now<<1|1].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<<1,l,r); else if(l>tree[now].mid) tree_change(now<<1|1,l,r); else { tree_change(now<<1,l,tree[now].mid); tree_change(now<<1|1,tree[now].mid+1,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<<1); tree_result(now<<1|1);}int main(){ read_int(n); for(int i=1;i<=n;i++) { read_int(do_l[i]); read_int(do_r[i]); maxn=max(maxn,do_r[i]); } tree_build(1,1,maxn); for(int i=1;i<=n;i++) { tree_change(1,do_l[i]+1,do_r[i]); } tree_result(1); int max_t=0,max_f=0,max_tt; for(int i=1;i<=cnt;i++) { if(!result[i]) { max_tt=1; for(int j=i+1;j<=cnt;j++) { if(result[j]==result[j-1]) max_tt++; else { if(result[j-1]) max_t=max(max_t,max_tt); else max_f=max(max_f,max_tt); max_tt=1; } } 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 0;}
AC日记——挤牛奶 洛谷 P1204
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。