CF356C

· · 题解

思路

当 $\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;
}