usaco Milking Cows 报告

题意：

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

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

• 最长至少有一人在挤奶的时间段。
• 最长的无人挤奶的时间段。（从有人挤奶开始算起）

题解：设置一个数组，表示当前时间点，初始化为0，每次读入起点终点，在起点处加一，终点减一，然后从开始遍历，用sum来加每一个时间点的值，sum是0的时候表示没有挤奶，sum大于0的时候表示在挤奶，然后就可以搞了

代码：

/*
ID:     lishicao
PROG:   milk2
LANG:   C++
*/
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std ;

int  vis[1000500] ;

ifstream fin  ( "milk2.in"  ) ;
ofstream fout ( "milk2.out" ) ;

int  main()
{
    int  N ;
    int  start , end , Max = 0 , Min = 99999999 , milked = 0 , notmilked = 0 ;
    memset( vis , 0 , sizeof( vis ) ) ;

    fin >> N ;
    while( N -- )
    {
        fin >> start >> end ;
        if( end > Max ) Max = end ;
        if( start < Min ) Min = start ;
        vis[start] ++ ;
        vis[end] --   ;
    }

    int  sum = 0 ;
    int  Count = 0 ;
    int  flag = 0 ;

    for( int i = Min ; i <= Max ; i ++ )
    {
        sum += vis[i] ;
        if( flag == 0 ){
            if( sum == 0 ) {
                flag = 1 ;
                if( milked < Count ) milked = Count ;
                Count = 0 ;
            }
            Count ++ ;
        }
        else{
            if( sum > 0 ) {
                flag = 0 ;
                if( notmilked < Count ) notmilked = Count ;
                Count = 0 ;
            }
            Count ++ ;
        }
    }
    fout << milked << " " << notmilked << endl ;
    return 0 ;
}