链接：https://ac.nowcoder.com/acm/contest/5668/A
来源：牛客网

题目描述：

There is a fishing game as following:

  • The game contains nn stages, numbered from 11 to nn.
  • 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.

  1. 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.
  2. 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.
  3. 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.
  4. You can do nothing.
    Now, you are given nn 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≤t≤2.5×1e5) --- the number of test cases.

There are two lines in each test. The first line contains one integer n (1≤n≤2×1e6), 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×1e6

输出描述：

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

solution：

题意：有n个水池
水池有四种类型：
1,0代表水池没有鱼和没有蛤蜊
2,1代表水池没有鱼但有蛤蜊
3,2代表有一条鱼但没有蛤蜊
4,3代表有鱼有蛤蜊
在每个水池中，你只能选择下面操作中的一种：
1.如果有蛤蜊，你可以捉蛤蜊做成诱饵
2.如果有鱼，你可以捕鱼，并且捕鱼不消耗诱饵
3.如果没有鱼，但是你有诱饵，你可以捕鱼，并消耗一包诱饵
4.什么都不做

问你最多能捕几条鱼？

经过分析我们可以知道水池有鱼的时候我们可以进行捕鱼操作，即使水池有鱼和蛤蜊，如果捉蛤蜊，你将会需要至少两个水池才能捕一条鱼，但是如果进行捕鱼，那么只会消耗一个水池，因此在有鱼的时候捕鱼是最优的。
然后我们可以把字符串从左到右进行遍历，设置一个变量count，在只有蛤蜊的情况下，count++，如果水池什么都没有，在count不为0的时候，count--，鱼的数量+1，遇到鱼则捕鱼。
在最后如果count还有剩余，说明在有些有蛤蜊的水池中我们可以进行捕鱼操作 鱼的数量+（count/2）

#include <iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<unordered_map>
#define INF 0x3f3f3f3f
#include<math.h>

using namespace std;
typedef long long ll;
typedef pair<int,int>P;

char s[2000010];
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d%s",&n,s);//cout<<s<<endl;
        int ans=0,cnt=0;
        for(int i=0;i<n;i++)
        {//cout<<cnt<<endl;
            if(s[i]=='0'&&cnt>0)
            {
                cnt--;ans++;
            }
            else if(s[i]=='1')cnt++;
            else if(s[i]=='2')ans++;
            else if(s[i]=='3')ans++;
        }
        if(cnt)ans+=cnt/2;
        printf("%d\n",ans);
    }
    return 0;
}