题目链接: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;
}