洛谷P1204 [USACO1.2]挤牛奶Milking Cows 前缀和

这题数据比较水暴搜都能够过去

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <string>
 6 #include <iostream>
 7 #include <iomanip>
 8 #include <cstring>
 9 using namespace std ;
10 
11 int n,x,y,mi,ma,now1,now2,ans1,ans2 ;
12 bool f[1000011] ;
13 
14 int main() 
15 {
16     scanf("%d",&n) ;
17     mi = 1000000000 ;  ma = 0 ;
18     for(int i=1;i<=n;i++) 
19     {
20         scanf("%d%d",&x,&y) ;
21         for(int j=x;j<=y;j++) f[ j ] = 1 ;
22         if( x<mi ) mi = x ;
23         if( y>ma ) ma = y ;
24     }
25     for(int i=mi;i<=ma;i++) 
26     {
27         if(f[i]) 
28         {
29             now1++;   now2 = 0 ;
30             if(now1-1>ans1) ans1 = now1-1 ;
31         }
32         else
33         {
34             now1 = 0;  now2++;
35             if(now2+1>ans2) ans2 = now2+1 ;
36         }
37      }
38     printf("%d %d
",ans1,ans2) ;
39     return 0 ;
40 }

但其实标算应该是一种前缀和的东西这个前缀和可以用来表示当前时间有几个人在挤奶

 1 #include <iostream>
 2 using namespace std;
 3 long long zt[1000001];
 4 int main(){
 5     ios::sync_with_stdio(false);
 6     long long now=0,sum=0,beg=1000000,end=0,n,lr,mn=0,mh=0;
 7     bool dy0=false;
 8     cin>>n;
 9     for (int i=0;i<n;++i){
10         cin>>lr;
11         ++zt[lr];
12         beg=min(beg,lr);
13         cin>>lr;
14         end=max(lr,end);
15         --zt[lr];
16     }
17     for (int i=beg;i<=end;++i){
18         now+=zt[i];
19         if (now>0&&!dy0){
20             dy0=true;
21             mn=max(sum,mn);
22             sum=0;
23         }
24         if (now==0&&dy0){
25             dy0=false;
26             mh=max(sum,mh);
27             sum=0;
28         }
29         ++sum;
30     }
31     cout<<mh<<' '<<mn<<endl;
32 }