题目大意

一个游戏包含n个阶段，每个阶段有四种类型：
类型0：没有鱼也没有蛤。
类型1：只有一只蛤。
类型2：只有一条鱼。
类型3：有一条鱼和一只蛤。

在每个阶段都可以执行四种操作之一：
1.用一只蛤换一包鱼饵。
2.如果有一条鱼，可以无需鱼饵抓到这条鱼。
3.无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。
4.跳过阶段。

要求求出每局游戏中能抓到鱼的最大条数。
给出样例数量（游戏次数）t (1≤t≤2.5×105)。每次游戏给出阶段数n(1≤n≤2×106)以及一个长度为n的字符串，s[i-1]为第i阶段的类型。n的总和不超过2×106。

解题思路

这里使用时间复杂度是O(n)的模拟。

首先考虑，在每个阶段所应该采取的操作。
显而易见，在类型3与4时，直接抓鱼永远是最佳选择。（直接白嫖永远第一）
但是在类型0时，只能通过鱼饵抓鱼；类型1时，可以换鱼饵或者用鱼饵抓鱼。

所以，我们先忽视前导0，在3或4时无脑在答案加1。
后面遇到一个0，就尽可能使用鱼饵；遇到1，就先默认制作鱼饵，将现在拥有的鱼饵数量加1。
最后如果有剩余鱼饵>=，则可以用2次类型1的多余阶段来再抓一条鱼（一次换鱼饵，一次抓鱼）。

AC代码


flag用来记录有没有遇到第一个类型1，flag==0时的0没有鱼饵，都要跳过。 
#include<bits/stdc++.h>
using namespace std;
int t,n,x,i,j,tot;
int main()
{
	string s;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		cin>>s;
		tot=x=i=0;
		bool flag=0;
		while(s[i]=='0') i++;
		for(;i<n;i++)
		{
			if(s[i]=='2' || s[i]=='3')
			{
				tot++;
				continue;
			}
			if(flag==0 && s[i]=='1') flag=1;
			if(flag==1 && s[i]=='1') x++;
			if(flag==1 && s[i]=='0' && x) tot++,x--;
		}
		if(x>=2) tot+=x/2;
		printf("%d\n",tot);
	}
    return 0;
}