POJ2454——Jersey Politics

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(0));
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n*3;i++)
            scanf("%d",&a[i].val),a[i].id=i;
        sort(a+1,a+1+n*3,cmp);
        int sum1=0,sum2=0;
        for(int i=1;i<=n;i++){
            sum1+=a[i].val;
            sum2+=a[i+n].val;
        }
        
        while(!(sum1>500*n&&sum2>500*n)){
            int x=rand()%n+1,y=rand()%n+n+1;
            sum1=sum1-a[x].val+a[y].val;
            sum2=sum2-a[y].val+a[x].val;
            swap(a[x],a[y]);
        }
        
        for(int i=1;i<=n*3;i++) printf("%d
",a[i].id);
    }
    return 0;
}