7.29 荣光

P11323 【MX-S7-T1】「SMOI-R2」Happy Card

需要观察到“炸”是三带一，即三张相同的牌可以带任意一张牌。

贪心地尽可能出三带一是对的，这点在模拟出牌后即可发现。

然后将牌分成 \(3\) 个一组，\(2\) 个一组，单独一组，分别讨论答案就好了。

code

const int N = 3e5 + 5;int T, n, v[N];
i64 cnt[4], ans;void init() {cnt[1] = cnt[2] = cnt[3] = 0; ans = 0;
}void solve() {read(n); init();rep(i, 1, n) read(v[i]);rep(i, 1, n) {cnt[3] += v[i] / 3;if (v[i] % 3) cnt[v[i] % 3]++;}if (cnt[3] <= cnt[1]) return write(cnt[3] + (cnt[1] - cnt[3]) + cnt[2], '\n'), void();if (cnt[3] - cnt[1] <= 2 * cnt[2]) return write(cnt[3] + (2 * cnt[2] - (cnt[3] - cnt[1]) + 1) / 2, '\n'), void();ans += cnt[2] * 2 + cnt[1];cnt[3] -= (2 * cnt[2] + cnt[1]);ans += (cnt[3] / 4) * 3; cnt[3] %= 4;if (cnt[3] == 3) ans += 3;else if (cnt[3] == 2 || cnt[3] == 1) ans += 2;write(ans, '\n');
}int main() {read(T);while (T--) solve();return 0;
}