题目回顾

我们有一个数组 $a_1, a_2, \dots, a_n$，可以：

1. 删除任意一个元素
2. 将一个元素的值增加 $1$

目标：使数组元素的和能被 $3$ 整除，求最少操作次数。

核心思路

设数组总和为 $s$，考虑 $s \bmod 3$ 的余数。

情况 1：$s \bmod 3 = 0$

此时已经满足要求，不需要任何操作。
答案 = 0

情况 2：$s \bmod 3 = 2$

要让总和能被 $3$ 整除，需要让 $s$ 增加 $1$（因为 $2+1=3$，模 $3$ 余 $0$）。

• 操作 2（增加 $1$）恰好做一次，就可以让总和增加 $1$。
• 也可以考虑删除一个元素，但删除会使总和减少，不一定更好。

结论：答案 = 1（因为一次增加操作即可）

情况 3：$s \bmod 3 = 1$

要让总和能被 $3$ 整除，需要让 $s$ 增加 $2$（因为 $1+2=3$），或者删除一个元素使得新总和模 $3$ 余 $0$。

子情况 3.1：存在一个元素 $a_i$ 满足 $a_i \bmod 3 = 1$

删除这个元素后，总和减少 $a_i$，减少量模 $3$ 余 $1$。
原来总和 $s \equiv 1 \pmod 3$，减去 $1$ 后 $s' \equiv 0 \pmod 3$。
一次删除操作即可。

子情况 3.2：不存在 $a_i \bmod 3 = 1$

我们无法通过一次删除得到模 $3$ 余 $0$ 的总和（因为删除余 $0$ 或 $2$ 的元素都不行）。
那么只能通过增加操作：
一次增加操作让总和 $+1$，两次增加操作让总和 $+2$。
因为需要总和 $+2$，所以需要两次增加操作（可以加在同一元素或不同元素上）。

结论：

• 若存在 $a_i \bmod 3 = 1$，答案 = 1
• 否则，答案 = 2

算法步骤

1. 输入 $t$
2. 对每个测试用例：
   • 计算总和 $ACC$
   • 同时检查是否存在元素 $x$ 满足 $x \bmod 3 = 1$，记录标志 $hv$
3. 根据 $ACC \bmod 3$ 判断：
   • 若为 $0$ → 输出 $0$
   • 若为 $2$ → 输出 $1$
   • 若为 $1$：
     • 若 $hv$ 为真 → 输出 $1$
     • 否则 → 输出 $2$

时间复杂度

• 每个测试用例 $O(n)$
• 总 $n$ 不超过 $2\times10^5$，完全可行。

代码实现（已给出）

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

int main(){
    int t;
    cin>>t;
    while(t--){
        int k;
        cin>>k;
        int ACC=0;
        bool hv=false;
        for(int i=0;i<k;i++){
            int x;
            cin>>x;
            ACC+=x;
            if(x%3==1){
                hv=true;
            }
        }
        if(ACC%3==0){
            cout<<0<<endl;
        }else if(ACC%3==2){
            cout<<1<<endl;
        }else{ // ACC%3 == 1
            if(hv==true){
                cout<<1<<endl;
            }else{
                cout<<2<<endl;
            }
        }
    }
}

总结

本题的关键是分类讨论总和模 $3$ 的余数，并结合删除和增加两种操作的最小代价：

一句话题解：
若总和能被 $3$ 整除，答案为 $0$；
若总和模 $3$ 余 $2$，答案为 $1$；
若总和模 $3$ 余 $1$，且存在模 $3$ 余 $1$ 的元素，答案为 $1$，否则答案为 $2$。