解题思路
一次操作会把某个货箱的重量改成另一个已存在的重量,因此最终能得到的重量集合,只能来自当前数组中已经出现过的模 3 余数。只需记录余数 0,1,2 是否出现过。
- 已经齐整:若当前总和 s≡0(mod3),直接输出
Yes。
- 出现过余数 0:把所有货箱都改成那个余数为
0 的重量,总和一定是 3 的倍数,输出 Yes。
- 只出现余数 1 或只出现余数 2:所有重量只能变成同一种余数,总和模
3 等于 n×1 或 n×2。当且仅当 n≡0(mod3) 时输出 Yes,否则 No。
- 同时出现余数 1 和 2:若 n=1,不可能;若 n≥2,总能配出若干个
1 与 2 使 1 的个数与 2 的个数模 3 相等(例如两两配对 1+2=3),输出 Yes。