暑假集訓Day4 B（貪心好題+二分答案）

題目連結在本地，題目大意是從一段隻包含0,1,2 的字元串中選出若幹個子序列“2020”，選出一個2020序列以後，這四個數字從原來的位置上删除，問最多能選出多少個這種序列。

一開始想的貪心思想是從左往右掃描，越靠左滿足2020的越先選出來，後來發現了反例就是20202200，如果越靠左滿足的越先選出來，那這個隻能選出一個2020，但是我們可以先選左邊的20，然後在後四個中取出一個20，另一個同理，是以這種貪心思想是錯誤的。

我們現在考慮另一種貪心思想，對于出現的2和0，我們一定把它當做第一個2和0，為什麼這麼做可以參考上面的反例。但是這個新的20不能全當新的，一定是到了一個數目為止，後面出現的20都作為第二個20，現在我們需要知道這個數是多少，這個步驟用二分做即可。

1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=1e5+5;
 4 int n,a[5];
 5 char s[MAX];
 6 bool feasible(int x){
 7     int i,j;
 8     a[1]=a[2]=a[3]=a[4]=0;
 9     for (i=1;i<=n;i++){
10         if (s[i]=='2'){
11             if (a[1]!=x) a[1]++;
12             else if (a[3]<a[2]) a[3]++;
13         }
14         if (s[i]=='0'){
15             if (a[2]!=x){
16                 if (a[2]<a[1]) a[2]++;
17             }
18             else{
19                 if (a[4]<a[3]) a[4]++;
20             }
21         }
22         if (a[4]==x) return true;
23     }
24     return false;
25 }
26                 
27 int main(){
28 //    freopen ("b.in","r",stdin);
29 //    freopen ("b.out","w",stdout);
30     int i,j,low,high,mid,ans;
31     while (scanf("%d",&n)!=EOF){
32         scanf("\n%s",s+1);
33         low=1,high=n;
34         ans=0;
35         while (low<=high){
36             mid=(low+high)>>1;
37             if (feasible(mid)){
38                 ans=mid;
39                 low=mid+1;
40             }
41             else high=mid-1;
42         }
43         printf("%d\n",ans);
44     }
45     return 0;
46