题目大意：有3k个数（1----3k），代表3k个城市，每个城市总共有1000票，给出3k个数代表X在每个城市能得到的票数，将其均分成3份，使得至少有2份中X能得到过半的票数，要求输出每份的城市编号

解题思路：要求至少有2份的票数之和过总和的一半，即求2份中票数之和大于500k（每个城市总票数为1000），则要使得票数和尽可能多，先贪心将最小的k个数筛掉，再用随机化将剩余的2k个数任意交换，使得最后每份的和大于500*k

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <string>
 
using namespace std;
 
struct node
{
    int nu,t;
}num[200],num1[100],num2[100],temp;
 
bool cmp(node a,node b)
{
    return a.nu>b.nu;
}
 
int main()
{
    int k,sum1=0,sum2=0,rd1,rd2;
    scanf("%d",&k);
    for(int i=0;i<3*k;i++)
    {
        scanf("%d",&num[i].nu);
        num[i].t=i;
    }
    sort(num,num+(3*k),cmp);
    for(int i=0;i<2*k;i+=2)
    {
        num1[i/2]=num[i];
        sum1+=num[i].nu;
    }
    for(int i=1;i<2*k;i+=2)
    {
        num2[i/2]=num[i];
        sum2+=num[i].nu;
    }
    while(sum1<=500*k||sum2<=500*k)
    {
        rd1=rand()%k;
        rd2=rand()%k;
        sum1=sum1-num1[rd1].nu+num2[rd2].nu;
        sum2=sum2-num2[rd2].nu+num1[rd1].nu;
        temp=num1[rd1];
        num1[rd1]=num2[rd2];
        num2[rd2]=temp;
    }
    for(int i=0;i<k;i++)
    {
        printf("%d\n",num1[i].t+1);
    }
    for(int i=0;i<k;i++)
    {
        printf("%d\n",num2[i].t+1);
    }
    for(int i=2*k;i<3*k;i++)
    {
        printf("%d\n",num[i].t+1);
    }
    return 0;
}