2020牛客暑期多校训练营(第三场)A.Clam and Fish
程序员文章站
2022-07-03 15:05:27
A.Clam and Fish题目链接-A.Clam and Fish题目大意一个游戏包含nnn个阶段,每个阶段有四种类型:类型000:没有鱼也没有蛤。类型111:只有一只蛤。类型222:只有一条鱼。类型333:有一条鱼和一只蛤在每个阶段都可以执行四种操作之一:用一只蛤换一包鱼饵。如果有一条鱼,可以无需鱼饵抓到这条鱼。无论在此阶段有没有鱼,都可以使用一包鱼饵捕获一条鱼。跳过该阶段请你求出每局游戏中能抓到鱼的最大条数解题思路贪心贪心贪心用ans记录抓到鱼的个数,cn...
A.Clam and Fish
题目链接-A.Clam and Fish
题目大意
一个游戏包含个阶段,每个阶段有四种类型:
类型:没有鱼也没有蛤。
类型:只有一只蛤。
类型:只有一条鱼。
类型:有一条鱼和一只蛤
在每个阶段都可以执行四种操作之一:
- 用一只蛤换一包鱼饵。
- 如果有一条鱼,可以无需鱼饵抓到这条鱼。
- 无论在此阶段有没有鱼,都可以使用一包鱼饵捕获一条鱼。
- 跳过该阶段
请你求出每局游戏中能抓到鱼的最大条数
解题思路
- 用
ans
记录抓到鱼的个数,cnt
记录鱼饵的个数 - 正序遍历字符串:
- 有鱼就抓(
白嫖难道不香吗) - 如果只有蛤,就做鱼饵(阶段先默认做鱼饵)
- 如果既没有鱼又没有蛤,就判断此时有没有鱼饵,如果有鱼饵就花一个鱼饵钓鱼
- 如果最后鱼饵有剩余(),就说明阶段做这些鱼饵的时间可以花一半时间来抓鱼,最后答案加上
cnt/2
即可 - 具体操作见代码
附上代码
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
string s;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n,cnt=0,ans=0;
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i]=='2'||s[i]=='3') ans++;
else if(s[i]=='1') cnt++;
else if(s[i]=='0'&&cnt){
ans++;
cnt--;
}
}
cout<<ans+cnt/2<<endl;
}
return 0;
}
本文地址:https://blog.csdn.net/Fiveneves/article/details/107552207
上一篇: 搜索引擎重复网页发现技术分析
下一篇: 可我昨晚值夜班没在家啊
推荐阅读
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
牛客多校第三场 A-Clam and Fish【贪心】+ B-Classical String Problem【思维】
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客多校第三场-J Just Shuffle
-
2020牛客多校第3场[Clam and Fish+贪心]
-
2020牛客多校第三场 E Two Matchings
-
2020牛客暑期多校训练营(第二场)Cover the Tree