牛客contest5668-A

传送门

题目大意

一个游戏包含n个阶段，每个阶段有四种类型：

1. 类型0：没有鱼也没有蛤。
2. 类型1：只有一只蛤。
3. 类型2：只有一条鱼。
4. 类型3：有一条鱼和一只蛤。

在每个阶段都可以执行四种操作之一：

1. 用一只蛤换一包鱼饵。
2. 如果有一条鱼，可以无需鱼饵抓到这条鱼。
3. 无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。
4. 跳过阶段。

要求求出每局游戏中能抓到鱼的最大条数。

思路

采用贪心的思想。首先，对于类型2、3，显然直接抓鱼是最优的，即有鱼抓鱼。但是类型0时只能用鱼饵抓鱼，类型1时只能做鱼饵或者用鱼饵抓鱼。

根据上面的分析，前导0是可以忽略的，因为我们什么都做不了。忽略后如果遇到类型2、3就直接答案++。其余情况下，优先用鱼饵抓鱼，其次用蛤来换鱼饵。在执行完整个过程后如果还有鱼饵，那么消耗两次类型1来换一条鱼。

值得注意的是，第一次遇见类型0时是没有鱼饵去捕鱼的，所以需要用一个bool来判断当前遇到类型0时是否有鱼饵。

#include <bits/stdc++.h>

using namespace std;

string s;
int t, n, bait, ans;

int main()
{
	scanf( "%d", &t );
	
	while ( t-- )
	{
		int i = 0; 
		scanf( "%d", &n );
		cin >> s;
		
		bool check = 0;
		while ( s[i] == '0' ) i++;
		
		for (i = i; i < n; i++ )
		{
			if ( s[i] == '2' || s[i] == '3' )
			{
				ans++;
				continue;
			}
			if ( check == 0 && s[i] == '1' ) check = 1;
			if ( check == 1 && s[i] == '1' ) bait++;
			if ( check == 1 && s[i] == '0' && bait )
			{
				ans++;
				bait--;	
			}
		}
		if ( bait >= 2 ) ans += bait / 2;
		printf( "%d\n", ans );
	}
	
	return 0;
}