2020牛客暑期多校训练营（第三场）A题

链接：https://ac.nowcoder.com/acm/contest/5668/A

来源：牛客网

#pragma warning (disable:4996)
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#define inf 0X3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn = 2e6 + 20;
string s;
int back[maxn];

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