ClamandFish

The first line contains one integer t ( $1 \le t \le 2.5 \times 10^5$ ) --- the number of test cases.

There are two lines in each test. The first line contains one integer n ( $1 \le n \le 2 \times 10^6$ ), indicating the number of stages in this game. The second line contains a string with length n. The i-th character of this string indicates the type of the i-th stage.

The sum of n across the test cases doesn't exceed $2 \times 10^6$ .

pypy3 解法, 执行用时: 1137ms, 内存消耗: 28276K, 提交时间: 2023-05-01 12:18:07

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ans = 0
    yuer = 0
    for i in range(n):
        if s[i] == '2' or s[i] == '3':
            ans += 1
        elif s[i] == '1':
            yuer += 1
        elif s[i] == '0' and yuer > 0:
            yuer -= 1
            ans += 1
    ans += yuer//2
    print(ans)

Python3(3.5.2) 解法, 执行用时: 1878ms, 内存消耗: 7404K, 提交时间: 2020-07-18 14:12:20

s1=int(input());
for i in range(s1):
    s2=int(input());
    s3=input();
    fish=0
    er=0
    kong=0
    for f in s3:
        if f=='2' or f=='3':
            fish+=1
        elif f=='1':
            er+=1
        else :
            if er>=1:
                er-=1
                fish+=1
    fish+=int(er/2)
    print(str(fish));

C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 2368K, 提交时间: 2020-07-27 13:26:30

#include<bits/stdc++.h>
using namespace std;

char s[2000005];

void solve() {
	int n;
	scanf("%d",&n);
	scanf("%s",s);
	int x=0,ans=0;
	for (int i=0;i<n;i++) {
		if (s[i]==49) x++;
		else if (s[i]>49) ans++;
		else if (x) ans++,x--;
	}
	printf("%d\n",ans+(x>>1));
}

int main() {
	int T;
	scanf("%d",&T);
	while (T--) solve();
}

C++(g++ 7.5.0) 解法, 执行用时: 586ms, 内存消耗: 4420K, 提交时间: 2023-05-01 13:44:43

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		string s;
		cin>>s;
		int ans=0,cnt=0;
		for(int i=0;i<s.size();i++){
			if(s[i]=='2'||s[i]=='3')ans++;
			else if(s[i]=='1')cnt++;
			else{
				if(cnt)cnt--,ans++;
			}
		}
		cout<<ans+cnt/2<<endl;
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 67ms, 内存消耗: 4272K, 提交时间: 2020-07-19 19:11:04

#include <cstdio>
const int N=2e6+10;
int T,n;
char s[N];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%s",&n,s+1);
		int ans=0,cl=0;
		for(int i=1;i<=n;i++){
			if(s[i]=='2'||s[i]=='3') ++ans;
			else if(s[i]=='0'&&cl>0) --cl,++ans;
			else if(s[i]=='1') ++cl;
		}printf("%d\n",ans+cl/2);			
	}
}

详情