题解 | #小红的数字删除#

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string str;
        cin >> str;
        int sum = 0;
        map<int, int> mp;
        for (char ch : str) {
            sum = sum + ch - '0';
            if (mp.count(ch - '0')) {
                mp[ch - '0'] = mp[ch - '0'] + 1;
            } else {
                mp[ch - '0'] = 1;
            }
        }
        if (sum < 3) {
            cout << 0 << endl;
            continue;
        }
        int ans = 0;
        int flag = 0;
        if (sum % 3 != 0) {
            for (int i = 1; i < 9; ++i) {
                // 有一个数，删除后大于等于3， 是3的倍数
                if (mp[i] > 0 && sum - i >= 3 && (sum - i) % 3 == 0) {
                    // 这个数只有一个，且在首位, 且第二位是0，暂时跳过
                    if (str[0] - '0' == i && mp[i] == 1 && str[1] == '0') {
                        flag = i;
                        continue;
                    }
                    mp[i]--;
                    ans++;
                    sum -= i;
                    break;
                }
            }
            if (flag) {
                mp[flag]--;
                ans++;
                sum -= flag;
                for (int i = 1; i < str.size(); ++i) {
                    if (str[i] != '0') {
                        break;
                    }
                    mp[0]--;
                }
            }
            // 没有数可以删除
            if (ans == 0) {
                cout << 0 << endl;
                continue;
            }
        }

        // 所有的0都可以
        ans += mp[0];
        // 1、先删除所有的3的倍数
        ans = ans + mp[3] + mp[6] + mp[9];
        // 2、计算一下，去除所有三的倍数后，剩下的数是否可以组成3的倍数。
        // 否则就留一个不删除
        if (sum - mp[3] * 3 - mp[6] * 6 - mp[9] * 9 < 3) {
            ans--;
        }
        cout << ans << endl;
    }

}
// 64 位输出请用 printf("%lld")

前导0的情况不好处理，