標記數組（哈希）

1e6的范圍，開一個char數組全然能夠，有人為1，無人為0，注意邊界就可以。最后線性掃描就可以。

時間復雜度，應該是O(n),n為最后結束的時間。

缺點就是……比較慢

/*ID:twd30651PROG:milk2LANG:C++ */ #include<iostream> #include<fstream> #include<string.h> #include<stdlib.h> char a[1000001]; using namespace std; int N; int main(int argc,char *argv[]) {freopen("milk2.in","r",stdin);freopen("milk2.out","w",stdout);scanf("%d",&N);memset(a,0,sizeof(a));int start;int end;int mins=1000000;int maxe=0;for(int i=0;i<N;++i){scanf("%d",&start);scanf("%d",&end);if(start<mins)mins=start;if(end>maxe)maxe=end;for(int j=start;j<end;++j)a[j]=1;}int max1=0;int max2=0;int l1=0;int l2=0;int flag1=1;int flag2=0;int i=1;//printf("%d %d\n",mins,maxe);for(i=mins;i<maxe;++i){if(flag1==a[i]){++l1;if(l1>max1)max1=l1;}elsel1=0;if(flag2==a[i]) {++l2;if(l2>max2)max2=l2;}else{l2=0;}}printf("%d %d\n",max1,max2);return 0; }

轉載于:https://www.cnblogs.com/brucemengbm/p/7223557.html

總結

以上是生活随笔為你收集整理的USACO 1.2 Milking Cows (枚举)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。