洛谷—— P1204 [USACO1.2]挤牛奶Milking Cows

https://www.luogu.org/problem/show?pid=1204

题目描述

三个农民每天清晨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：

900 300

说明

题目翻译来自NOCOW。

USACO Training Section 1.2

时间区间我用的左闭右开、

线段树区间修改，最后统计最大值、

 #include <cstdio>

 #define max(a,b) (a>b?a:b)

 const int N();

 int n,cnt,l[N],r[N],have[N];

 struct Tree {

     bool flag;

     int l,r,val;

 }tr[N<<];

 #define lc (now<<1)

 #define rc (now<<1|1)

 #define mid (tr[now].l+tr[now].r>>1)

 void Tree_build(int now,int l,int r)

 {

     tr[now].l=l; tr[now].r=r;

     if(l==r)

     {

         tr[now].val=;

         tr[now].flag=;

         return ;

     }

     Tree_build(lc,l,mid);

     Tree_build(rc,mid+,r);

 }

 void Tree_down(int now)

 {

     if(tr[now].l==tr[now].r) return ;

     tr[lc].flag=; tr[lc].val=;

     tr[rc].flag=; tr[rc].val=;

 }

 void Tree_add(int now,int l,int r)

 {

     if(tr[now].l==l&&tr[now].r==r)

     {

         tr[now].val=;

         tr[now].flag=;

         return ;

     }

     if(tr[now].flag) Tree_down(now);

     if(r<=mid) Tree_add(lc,l,r);

     else if(l>mid) Tree_add(rc,l,r);

     else Tree_add(lc,l,mid),Tree_add(rc,mid+,r);

 }

 void Tree_push(int now)

 {

     if(tr[now].l==tr[now].r)

     {

         have[++cnt]=tr[now].val;

         return ;

     }

     if(tr[now].flag) Tree_down(now);

     Tree_push(lc); Tree_push(rc);

 }

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(;ch>''||ch<'';) ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';

 }

 int AC()

 {

     int R=; read(n);

     for(int i=; i<=n; ++i)

     {

         read(l[i]);read(r[i]);

         R=max(R,r[i]);

     }

     Tree_build(,,R);

     for(int i=; i<=n; ++i)

         Tree_add(,l[i]+,r[i]);

     Tree_push();

     int ans1=,ans2=,tmp;

     for(int i=; i<=cnt; ++i)

     {

         if(have[i]) continue;

         tmp=;

         for(int j=i+; j<=cnt; j++)

         {

             if(have[j]==have[j-]) tmp++;

             else

             {

                 if(have[j-]) ans2=max(ans2,tmp);

                 else ans1=max(ans1,tmp);

                 tmp=;

             }

         }

         if(have[cnt]) ans2=max(ans2,tmp);

         else ans1=max(ans1,tmp);

         break;

     }

     printf("%d %d\n",ans1,ans2);

     return ;

 }

 int Hope=AC();

 int main(){;}

巴特西

洛谷—— P1204 [USACO1.2]挤牛奶Milking Cows

https://www.luogu.org/problem/show?pid=1204

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章