2020牛客暑期多校训练营（第三场） A-Clam and Fish
Clam and Fish
https://ac.nowcoder.com/acm/contest/5668/A
题目大意
一个游戏包含n个阶段，每个阶段有四种类型：
类型0：没有鱼也没有蛤。
类型1：只有一只蛤。
类型2：只有一条鱼。
类型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;
}2020牛客暑期多校训练营 文章被收录于专栏
只是题解，可参考，可学习，可点赞:)
投递快手等公司10个岗位 >
