usaco_milk2.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROG: milk2
LANG: C++
*/

#include<iostream>
#include<cstring>
#include<fstream>

using namespace std;
int main()
{
 ifstream fin("milk2.in");
 ofstream fout("milk2.out");
 int i,j,k,n,lt,rt,max_feed=0,max_left=0,maxt=0,mint=1000000,maxlt=0,maxrt=0,maxlr=0;
 bool a[1000001];
 fin>>n;
 memset(a,false,sizeof(a));
 for(i=1;i<=n;i++)
 {
     fin>>lt>>rt;
     for(j=lt;j<=rt;j++) a[j]=true;
     if(rt>maxt) maxt=rt;
     if(rt-lt>maxlr) {maxlt=lt;maxrt=rt;maxlr=rt-lt;}
     if(lt<mint) mint=lt;
 }
 bool now=a[mint]; 
 int max=mint,min=mint;
 if(n==1) fout<<rt-lt<<' '<<'0'<<endl;
 else
 {
 for(i=mint;i<=maxt;i++)
 {    
     if(a[i]==now && i<maxt) {}     
     else
     { if(now)
       {
         if(i-min>max_feed)
         {if(i<maxt) 
             {max_feed=(i-1)-min; min=i-1;}
          else
              {max_feed=i-min;min=i;}
          }
          if(i<maxt) 
             {min=i-1;}
          else
              {min=i;}
       }
       else 
         if(i-min>max_left) {max_left=i-min; min=i;}
         else min=i;
      // max=1;
     }
     now=a[i];
 }
 if(now && max>max_feed) {max_feed=(i-1)-min;}
 //else if(!now && max>max_left) {max_left=(i-1)-min;}
 if(max_feed==0) {max_feed=maxlr;}
 if(maxt-mint==max_feed && maxlr==max_feed) {fout<<maxrt-maxlt<<' '<<'0'<<endl;}
 else if(maxt-mint==max_feed && maxlr<max_feed) {fout<<maxrt-maxlt<<' '<<'1'<<endl;}
 else fout<<max_feed<<' '<<max_left<<endl;
}
 //system("PAUSE");
 return 0;
}