欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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
2020牛客暑期多校训练营(第三场)A.Clam and Fish
2020牛客暑期多校训练营(第三场)A.Clam and Fish
2020牛客暑期多校训练营(第三场)A.Clam and Fish
题目大意
一个游戏包含nn个阶段,每个阶段有四种类型:
类型00:没有鱼也没有蛤。
类型11:只有一只蛤。
类型22:只有一条鱼。
类型33:有一条鱼和一只蛤
在每个阶段都可以执行四种操作之一:

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

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

解题思路
贪心

  • ans记录抓到鱼的个数,cnt记录鱼饵的个数
  • 正序遍历字符串:
  1. 有鱼就抓(白嫖难道不香吗 )
  2. 如果只有蛤,就做鱼饵(11阶段先默认做鱼饵)
  3. 如果既没有鱼又没有蛤,就判断此时有没有鱼饵,如果有鱼饵就花一个鱼饵钓鱼
  • 如果最后鱼饵有剩余(>1>1),就说明11阶段做这些鱼饵的时间可以花一半时间来抓鱼,最后答案加上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