首页 > 代码库 > Codeforces 439C Devu and Partitioning of the Array(模拟)

Codeforces 439C Devu and Partitioning of the Array(模拟)

题目链接:Codeforces 439C Devu and Partitioning of the Array 


题目大意:给出n个数,要分成k份,每份有若干个数,但是只需要关注该份的和为奇数还是偶数,要求偶数堆的个数为p。输出方案。


解题思路:首先先将数组按照奇偶排序,也可以分开储存。然后先单独分k-p个奇数,然后后面的就将两个奇数当一个偶数分配,分配过程中计算是否满足,比如说奇数是否成对,以及是否分成了k堆。


#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e5 + 5;

int n, k, p, d[N];
vector<int> g[N];

inline bool cmp (const int& a, const int& b) {
    return (a&1) > (b&1);
}

void init () {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 0; i < n; i++)
        scanf("%d", &d[i]);

    sort(d, d + n, cmp);
    for (int i = 0; i < k; i++)
        g[i].clear();
}

bool judge () {
    int mv = 0;
    for (int i = 0; i < k - p; i++) {
        if (d[mv]&1)
            g[i].push_back(d[mv++]);
        else
            return false;
    }

    int t = k - p;
    while (mv < n) {

        t %= k;

        if (d[mv]&1) {
            g[t].push_back(d[mv++]);

            if ((d[mv]&1) != 1 || mv >= n)
                return false;

            g[t].push_back(d[mv++]);
        } else {
            g[t].push_back(d[mv++]);
        }
        t++;
    }

    if (g[k-1].size() == 0)
        return false;
    return true;
}

int main () {
    init();

    if (judge()) {
        printf("YES\n");
        for (int i = 0; i < k; i++) {
            printf("%lu", g[i].size());
            for (int j = 0; j < g[i].size(); j++)
                printf(" %d", g[i][j]);
            printf("\n");
        }
    } else
        printf("NO\n");

    return 0;
}