随机化算法+贪心！
将3*k排序后分成3分，将第二第三份的和分别加起来，让和与500*k比较，都大于则输出，否则，随机生成2个数，在第二第三份中交换！
代码如下：
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
struct an
{
int w,lab;
}p[];
bool cmp(const an &a,const an &b)
{
return a.w<b.w;
}
int main()
{
int i,j,n,sa,sb,ans,a,b;
cin>>n;
for(i=;i<*n;i++){
cin>>p[i].w;
p[i].lab=i+;
}
sort(p,p+*n,cmp);
sa=;sb=;
for(i=n;i<n+n;i++)
sa+=p[i].w;
for(i=n+n;i<*n;i++)
sb+=p[i].w;
ans=n*;
bool flag=;
if(sa>ans&&sb>ans) flag=;
while(!flag){
a=rand()%n+n;
b=rand()%n+*n;
sa=sa-p[a].w+p[b].w;
sb=sb-p[b].w+p[a].w;
swap(p[a],p[b]);
if(sa>ans&&sb>ans){
flag=;
break;
}
}
for(i=;i<*n;i++)
cout<<p[i].lab<<endl;
return ;
}