【USACO题库】1.2.1 Milking Cows挤牛奶

   一开始认为过不了，后来交就AC了。

1007. 【USACO题库】1.2.1 Milking Cows挤牛奶
(File IO): input:milk.in output:milk.out

题目描述

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

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

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

最长的无人挤奶的时间段。

输入

第一行一个整数N。

接下来N+1行，每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。

输出

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

样例输入

3

300 1000

700 1200

1500 2100

样例输出

900 300

先来看道题：

马路旁的树

 

题目描述

某学校有一条“春秋大道”，其道路两旁对称地栽有树木。现在为了保证整体的美观，需要移除其中的一些树。因此有必要统计，在移除一些树木之后，春秋大道上还有多少棵树。

为了简化问题，把春秋大道想象成一条数轴，数轴坐标为1 ~ n。

尚未进行移除操作时，每个坐标点上有两棵树。

给一次移除操作(x y)，将会把[x,y]区间上所有的树移除。

最终需要统计，在所有移除操作完成以后，还剩有多少棵树。

输入

第一行为一个整数n( 1<= n <= 1000 )。

第二行为一个整数k( 1<= k <= 100)，代表移除操作的个数。

下面k行，每行有两个整数x，y ( 1 <= x < =y <= n)，中间有一个空格分隔开，代表把[x,y]区间上的所有树移除。

输出

输出所有移除操作完成之后，道路两旁还剩树的数目总数。

注意：是道路两旁！

样例输入

5

2

1 3

4 5

样例输出

0

这两道题，有异曲同工之妙。

思路：

只需要一个a数组， 比如说：100~200 那么a[100]~a[199]都标记为1，其余为零， 以此类推，当所有的时间都标记完了之后，我们就可以开始统计了。（标记法）

代码如下：

#include<bits/stdc++.h>
using namespace std; 
const int maxn=1000010; 
bool a[maxn]; int t=0; 
int n,ans1=0,ans2=0; int x,y;
int maxx=0,minx=maxn; 
int main() 
{ 
  freopen("milk.in","r",stdin);
  freopen("milk.out","w",stdout);
  scanf("%d",&n); 
  for(int i=1;i<=n;i++)
  { 
      scanf("%d",&x); 
    scanf("%d",&y); 
    minx=min(x,minx); 
    maxx=max(y,maxx); 
    for(int j=x;j<y;i++) a[j]=1; 
  }
  int p=minx; 
  int q=maxx; 
  for(int i=p;i<=q;i++) 
  { 
    if(a[i]==1) t++; 
    else
    {
      ans1=max(ans1,t);
      t=0; 
    }
  } 
  for(int i=p;i<=q;i++) 
  { 
    if(a[i]==0)t++; 
    else 
    { 
      ans2=max(ans2,t); 
      t=0; 
    }  
  } 
  cout<<ans1<<" "<<ans2<<endl;
}