【题目大意】
给你一组各不相同的数列，问你是否能够将这个数列划分为k个不相交的非空集合，使得其中的p个集合中的所有元素的和为偶数，剩下的k-p个集合中的所有元素的和为奇数。
注意：集合不需要连续。
如果阵列存在这种划分，给出所有可能的有效划分。
n------------代表有n个整数
k------------代表划分为k部分
p------------代表有p个集合的和为偶数
如果存在这样的划分，输出"YES"，然后输出k行，每行包含：第一个数为这个集合的大小n，接着是n个这个集合中的元素，集合内元素输出不考虑顺序。
否则输出"NO"。
可能存在多个有效的划分，输出其中一个即可。
【题目分析】
其实就是维持奇偶的个数，n种情况判断一下，加维护集合个数。
首先来分析：
几个数相加无非存在这三种情况： 奇+奇=偶 奇+偶=奇 偶+偶=偶
多余的偶数无意义，用贪心将偶数尽量消耗掉。
然后再去构造奇数。
我们用int odd来记录奇数的个数，
那么我们用这些奇数来构造奇数组，
如果odd>=k-p(k-p为需要的奇数组)，并且构造完这些奇数组后剩余的奇数的个数为a个，如果a为偶数，那么我们可以用这a个奇数去构造a/2个偶数。
同时，我们用even来表示偶数的个数，
那么如果even+a/2>=p，就一定存在这样的划分，现在就可以输出"YES"了。
这些判断用一条语句就能实现：
if(odd>=(k-p)&&(odd-(k-p))%2==0&&(even+(odd-(k-p))/2)>=p)
然而，这不是重点，重点在于这些集合的分配。
方法一：
#include <iostream> #include <cstring> #include <stdio.h> #include<algorithm> using namespace std ; int n,k,p; int c[100005],even[100005],odd[100005]; int main() { //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&k,&p); p=k-p; int t1=0,t2=0; for(int i=1; i<=n; i++) { scanf("%d",c+i); if(c[i]&1)odd[++t1]=c[i]; else even[++t2]=c[i]; } if(t1<p||(t1>p&&(t1-p)%2))puts("NO"); else if((t1-p)/2+t2<k-p)puts("NO"); else { puts("YES"); if(k-p) { int t=0,ct=0; for(int i=1; i<=p; i++) { printf("1 %d ",odd[++t]); } for(int i=1; i<=k-p-1; i++) { if(t<t1) { printf("2 %d %d ",odd[t+1],odd[t+2]); t+=2; } else printf("1 %d ",even[++ct]); } int f=t1-t; int d=t2-ct+f; printf("%d",d); for(int i=1; i<=d; i++) { if(t<t1) { printf(" %d %d",odd[t+1],odd[t+2]); t+=2; i++; } else printf(" %d",even[ct+i-f]); } puts(""); } else { int t=0; for(int i=1;i<=p-1;i++) { printf("1 %d ",odd[++t]); } int f=t1-t; int d=f+t2; printf("%d",d); for(int i=1;i<=d;i++) if(t<t1)printf(" %d",odd[++t]); else printf(" %d",even[i-f]); puts(""); } } return 0; }
方法二：
本人觉得这个方法要比方法一巧妙的多。也是贪心，不过这个是先奇后偶。
#include<bits/stdc++.h> #define LL long long #define MAX 100010 using namespace std; struct Node { LL a; //值 bool b; //奇偶标记 }; Node num[MAX]; bool cmp(Node a,Node b) { return a.b>b.b; } int main() { LL n,k,p; cin>>n>>k>>p; LL i,j; LL odd=0,even=0; for(i=0;i<n;i++) { cin>>num[i].a; if(!(num[i].a%2)) { num[i].b=0; even++; } else { num[i].b=1; odd++; } } if(odd>=(k-p)&&(odd-(k-p))%2==0&&(even+(odd-(k-p))/2)>=p) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; return 0; } sort(num,num+n,cmp); //按照奇偶来排序，奇数在前 if(p==0) { int cnt=0; for(i=1;i<=k;i++) //控制组数 { if(i!=k) //总是输出一个 { cout<<"1 "<<num[cnt++].a<<endl; } else { cout<<n-cnt<<endl; for(i=cnt;i<n;i++) cout<<" "<<num[i].a; } } return 0; } int cnt=0; for(i=1;i<=k;i++) //控制组数 { if(i<=k-p) //先将奇数组输完 { cout<<"1 "<<num[cnt++].a<<endl; } else if(i>k-p&&i<k) //奇数组已经输完 { if(num[cnt].b) //多余的奇数两两构成偶数组输出 cout<<"2 "<<num[cnt++].a<<" "<<num[cnt++].a<<endl; else //奇数已输完，现在要输出单个偶数 cout<<"1 "<<num[cnt++].a<<endl; } else //把剩余的全部输出 { cout<<n-cnt; for(j=cnt;j<n;j++) cout<<" "<<num[j].a; cout<<endl; } } return 0; }