POJ2454——Jersey Politics

题目大意：

在泽西奶牛和荷斯坦奶牛的最新普查中，威斯康星奶牛在谷仓中获得了三个档位。 泽西奶牛目前控制着国家重新分配委员会。 他们想将国家分为三个相当大的投票地区，以便保证泽西奶牛在至少两个地区获得选举权。 
威斯康星州有3 * K（1 <= K = = 60）个1000头牛的城市，编号为1..3 * K，每头都有泽西奶牛的已知数量（范围：1.001）。 找到一种将州划分为三个区域的方式，每个区域都有K个城市，使得泽西奶牛在至少两个地区拥有多数比例。 
所有提供的输入数据集都可以解决。

随机化+贪心

按照价值从大到小排序，显然只能保证第一段满足，第二段不一定满足，那么随机两个数，x属于第一段，y属于第二段，交换知道满足题意为止。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<ctime>

#define N 10000000

using namespace std;

int n;

struct node{

    int id,val;

}a[N];

bool cmp(node A,node B){

    return A.val>B.val;

}

int main()

{

    srand(time());

    while(scanf("%d",&n)!=EOF){

        for(int i=;i<=n*;i++)

            scanf("%d",&a[i].val),a[i].id=i;

        sort(a+,a++n*,cmp);

        int sum1=,sum2=;

        for(int i=;i<=n;i++){

            sum1+=a[i].val;

            sum2+=a[i+n].val;

        }

        while(!(sum1>*n&&sum2>*n)){

            int x=rand()%n+,y=rand()%n+n+;

            sum1=sum1-a[x].val+a[y].val;

            sum2=sum2-a[y].val+a[x].val;

            swap(a[x],a[y]);

        }

        for(int i=;i<=n*;i++) printf("%d\n",a[i].id);

    }

    return ;

}