2020牛客暑期多校训练营（第三场）A

题目描述

There is a fishing game as following.
The game contains $n$ stages, numbered from $1$ to $n$ .
There are four types of stages (numbered from $0$ to $3$ ). Type $0$ : There are no fish and no clam in this stage. Type $1$ : There are no fish and one clam in this stage. Type $2$ : There are one fish and no clam in this stage. Type $3$ : There are one fish and one clam in this stage.
In each stage, you can do exactly one of the following four actions.
If there is a clam in the stage, you can use this clam to make one pack of fish bait. And the number of packs of fish bait you have is increased by one. You can use this pack of fish bait to catch fish after this stage.
If there is one fish in the stage, you can catch this fish without any fish bait. After this stage, the number of packs of fish bait you have is not changed.
If you have at least one pack of fish bait. You can always catch one fish by using exactly one pack of fish bait even if there are no fish in this stage. After this stage, the number of packs of fish bait you have is decreased by one.
You can do nothing.
Now, you are given $n$ and the type of each stage. Please calculate the largest number of fish you can get in the fishing game.

输入描述

The first line contains one integer $t$ ( $1 \leqslant t \leqslant 2.5 \times 10^5$ ), indicating the number of test cases.
There are two lines in each test. The first line contains one integer $n$ ( $1 \leqslant n \leqslant 2 \times 10^6$ ), indicating the number of stages in this game. The second line contains a string with length $n$ . The $i$ -th character of this string indicates the type of the $i$ -th stage.
The sum of $n$ across the test cases doesn't exceed $2 \times 10^6$ .

输出描述

For each test case print exactly one integer indicating the maximum number of fish you can catch in the game configuration.

示例1

输入

输出

2  
0

备注

One possible scenario you can catch two fishes is as follow.
stage $1$ : Do nothing.
stage $2$ : Make a pack of fish bait.
stage $3$ : Catch a fish by a pack of fish bait.
stage $4$ : Catch the fish that appears in the stage.

分析

首先明确，要是当前的状态有鱼，那么直接抓鱼。若当前为状态 $2$ ，那么用鱼饵钓鱼显然不如直接抓鱼实惠；若当前状态为 $3$ ，虽然可以获得鱼饵，但是获得鱼饵也是为了在将来花费这个鱼饵钓到鱼，问题是将来可能不会再有钓鱼的机会（鱼饵多余，已经是最后一天……），不如放弃这个鱼饵，直接抓鱼。
若当前状态没有鱼，那么鱼饵要尽量在没有蛤蜊的时候用掉，有蛤蜊的状态用来获取鱼饵。若当前状态为 $0$ ，什么都没有；那么有鱼饵的话直接用来抓鱼，否则就什么都不做。若当前状态为 $1$ ，如果没有鱼饵，那就不必思考，直接获取鱼饵；如果有鱼饵，再来考虑要不要钓鱼；因为鱼饵是为将来状态为 $0$ 的时候准备的，如果钓鱼后，拥有的鱼饵足够将来状态为 $0$ 的那几天使用，就可以放心地钓鱼，否则就将蛤蜊做成鱼饵。
值得一提的是，需要逆向预处理第 $i$ 天后状态为 $0$ 的天数，再正向进行贪心。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第三场） Problem A
Date: 8/14/2020
Description: Greedy
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2000005;
int _;
char days[N];
int n;
int leftover[N];
int bait,fish;
inline void init();
int main(){
    for(cin>>_;_;_--){
        scanf("%d%s",&n,days+1);
        init();
        int i;
        for(i=n;i>=1;i--){
            leftover[i]+=days[i]=='0';
            leftover[i]+=leftover[i+1];
        }
        for(i=1;i<=n;i++){
            if(days[i]=='0'){
                //没鱼 没蛤蜊
                if(bait){
                    //有鱼饵 可以抓鱼
                    bait--;
                    fish++;
                }
            }else if(days[i]=='1'){
                //没鱼 有蛤蜊
                if(!bait){
                    //没鱼饵 只能将蛤蜊做成鱼饵
                    bait++;
                }else{
                    //有鱼饵 考虑要不要抓鱼
                    if(leftover[i]<bait){
                        //当前鱼饵足够在后面没鱼没蛤蜊的情况下抓鱼
                        //现在可以抓鱼
                        fish++;
                        bait--;
                    }else{
                        //做成鱼饵 在将来没鱼没蛤蜊的情况下抓鱼
                        bait++;
                    }
                }
            }else{
                //有鱼直接抓 不能错失机会
                fish++;
            }
        }
        printf("%d\n",fish);
    }
    return 0;
}
inline void init(){
    bait=fish=0;
    fill(leftover,leftover+n+2,0);
}