洛谷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\n",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 }

轉載于:https://www.cnblogs.com/third2333/p/6814891.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/541429.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/541429.shtml
英文地址，請注明出處：http://en.pswp.cn/news/541429.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！