POJ 2454

题意：给你一个3*k大小的数组

找出一个序列使得至少其中两组k大小的数组的总和>500*k;

先排序找出最小的序列号。

再在剩下的2*k里随机

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
int a[200],c[200];
void swap(int *a,int *b)
{
   int tmp;
   tmp=*a;
   *a=*b;
   *b=tmp;
}
void quick_sort(int a[], int l, int r)//从大到小快速排序
{
   int i,j;
   int val;
   if(l<r){
      i=l;
      j=r;
      val=a[l];
      while(i<j){
         while(i<j && a[j] <= val)
            j--;
         if(i<j){
            a[i]=a[j];
            i+=1;
         }
         while(i<j && a[i] > val)
            i++;
         if(i<j){
            a[j]=a[i];
            j-=1;
         }
      }
      a[i]=val;
      quick_sort(a,l,i-1);
      quick_sort(a,i+1,r);
   }
}

int main(int argc, char* argv[])
{
   int k;
   int i;
   int cnt1,cnt2,x,y;
   if(NULL==freopen("poj2454i.txt","r",stdin))
      return -1;
   scanf("%d",&k);
   for(i=1;i<=3*k;i++){
      scanf("%d",&a[i]);
      c[i]=i;
   }
   quick_sort(a,1,3*k);
   while(1){
      cnt1=0;
      cnt2=0;
      for(i=1;i<=k;i++)
         cnt1 += a[c[i]];
      for(i=k+1;i<= 2*k; i++)
         cnt2 += a[c[i]];
      if(cnt1 > k*500 && cnt2 > k*500){
         for(i=1;i<=3*k;i++)
            printf("%d\n",c[i]);
         break;//找到一个匹配终止整个循环
      }
      x=rand()%k+1;
      y=rand()%k+k+1;
      swap(&c[x],&c[y]);
   }
   return 0;
}
2
510
500
500
670
400
310
1
4
3
2
5
6

也可以用搜索，不过我现在没想好怎么做。