本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-21 12:09:02

思路

$p_i$ 表示i的出现次数。

当 $\sum a_i < 3$ 或 $\sum a_i = 5$ 就是 -1。

当 $p_1 \ge p_2$

答案加上 $p_2$。

答案再加上 $\frac{p_1}{3} \times 2$，因为三个合并成一个，要合并两次，所以要再乘 $2$。

当 $p_1 = 1$

当 $p_3 \not = 0$

答案加一，把这个 $1$ 放到一个三里面。

否则答案加二，因为要把两个 $4$ 每个拿出一个 $1$ 给他，所以有两次。

当 $p_1=2$

答案加上 $2$，因为要么是把他两个合并，一次在把一个 $4$ 里拿出一个 $1$，或者把他们分别合成在一个三里，所以都是需要两次。

然后当 $p_1 < p_2$ 类似的搞一搞就好了。

CODE:

#include <bits\/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
int a[N], p[N];\/\/p[i]表示i的出现次数
int main() {
    scanf("%d", &n);
    int sum = 0;\/\/总和最多是4*10^6
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
        p[a[i]]++;
    }
    if (sum == 1 || sum == 2 || sum == 5) {\/\/sum不够3个，或分不成3个和4个
        puts("-1");
        return 0;
    }
    int ans = 0;
    if (p[1] >= p[2]) {
        ans += p[2];
        p[1] -= p[2];\/\/把p[2]个2和p[2]个1构成三个
        ans += p[1] \/ 3 * 2;\/\/要把p[1]里三个合成一个，因为要说服另外两个，所以再乘2
        p[3] += p[1] \/ 3;\/\/3的个数加上它里面有多少个。
        p[1] %= 3;
        if (p[1] == 1) {
            if (p[3] >= 1)
                ans++;\/\/表示有一个3，可以直接说服，然后把他放到某个有三个人的房间里。
            else
                ans += 2;\/\/否则就要把两个4每一个都说服一个来。
        }else if (p[1] == 2)
            ans += 2;\/\/因为不管是把两个一合并到一个，再从四里拿过来一个，还是
    }else {\/\/同1的处理方法
        ans += p[1];
        p[2] -= p[1];
        ans += p[2] \/ 3 * 2;
        p[3] += p[2] \/ 3;
        p[2] %= 3;
        if (p[2] == 1) {
            if (p[4] >= 1)
                ans += 1;
            else
                ans += 2;
        }
        else if (p[2] == 2)
            ans += 2;
    }
    printf("%d\n", ans);
    return 0;
}