poj2454:http://poj.org/problem?id=2454
题意：给你3*k个数，然后让你分成三堆，使得至少其中的两堆中的数字之和大于500*k。
题解：这道题一开始我并不知道怎么做，准备采用随机算法，初始化的时候使其分成3堆，然后每次从每一堆中rand一个数，依次的进行交换，但是交了几版，发现都是wa。最后
才知道要用贪心。把数字进行降序排序，然后把前2*k个给两堆，只要前两堆都满足大于500*k，如果不满足，那么对于更小的数的组合就不可能满足了。然后最前两堆进行随机算法
每次rand一个，然后相互交换，找到满足条件的即可！
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int kind[182]; 7 int k,timelimit; 8 int sum1,sum2; 9 struct Node { 10 int w; 11 int id; 12 }node[182]; 13 int cmp(Node a,Node b ){ 14 return a.w>b.w; 15 } 16 int main(){ 17 scanf("%d",&k); 18 sum1=sum2; int t; 19 timelimit=1000;memset(kind,0,sizeof(kind)); 20 for(int i=1;i<=3*k;i++){ 21 scanf("%d",&node[i].w); 22 node[i].id=i; 23 } 24 sort(node+1,node+3*k+1,cmp); 25 for(int i=1;i<=3*k;i++){ 26 if(i<=k){ 27 kind[i]=1; 28 sum1+=node[i].w; 29 } 30 else if(i<=2*k){ 31 kind[i]=2; 32 sum2+=node[i].w; 33 } 34 } 35 if(sum1>500*k&&sum2>500*k)t=0; 36 else t=timelimit*100; 37 while(t--){ 38 int a,b; 39 while(true){ 40 a=rand()%(3*k)+1; 41 if(kind[a]==1)break; 42 } 43 while(true){ 44 b=rand()%(3*k)+1; 45 if(kind[b]==2)break; 46 } 47 sum1+=node[b].w-node[a].w,kind[a]=2; 48 sum2+=node[a].w-node[b].w,kind[b]=1; 49 if(sum1>500*k&&sum2>500*k)break; 50 } 51 for(int i=1;i<=3*k;i++) 52 if(kind[i]==1)printf("%d\n",node[i].id); 53 for(int i=1;i<=3*k;i++) 54 if(kind[i]==2)printf("%d\n",node[i].id); 55 for(int i=1;i<=3*k;i++) 56 if(kind[i]==0)printf("%d\n",node[i].id); 57 58 }