A 贪心

思路

奉行原则：

  • 2，3阶段有鱼直接白嫖，没鱼选择0，1阶段钓鱼。我们以屯着的鱼饵最少为原则，尽可能钓更多的鱼：
  • 0阶段：有鱼饵就钓鱼
  • 1阶段：无脑屯鱼饵
  • 如果鱼饵数目多余，可以用多余的1阶段来钓鱼。

代码

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, t;
    string s;
    cin >> t;
    while (t--) {
        int fish = 0, bait = 0;
        cin >> n >> s;

        for (char ch : s) {
            if (ch == '0') {
                // 0 fish 0 clam
                if (bait) bait--, fish++;
            } else if (ch == '1') {
                // 0 fish 1 clam
                bait++;
            } else if (ch == '2') {
                // 1 fish 0 clam
                fish++;
            } else {
                // 1 fish 1 clam
                fish++;
            }
        }
        fish += bait / 2;
        cout << fish << '\n';
    }
    return 0;
}