Description

# [USACO05FEB] Jersey Politics G 

什么鬼原题意。。。看了我二十分钟 

题意重编by hansang，有错欢迎指出

spj by:hdh

## 题目描述 

在奶牛州，要开始选举州长。共有 $3 \times k$ 个城市，依次标号为 $1, 2, \cdots, 3 \times k$，每个城市各有 $1000$ 个选民。候选者贝西在这些城市中各占有 $w _ 1, w _ 2, \cdots, w _ {3 \times k}$个支持者。 

这些城市将平分为 $3$ 组，此时每**组**城市中有 $1000 \times k$ 个选民。当一个候选者在至少两组城市中，支持他的人总数**严格大于**该组城市总选民数的一半， 他就被选举为州长。 

贝西想请你帮忙，找一种合理分配三组城市的方法，让她能当上州长。

数据保证有解。

## 输入格式 

第一行一个整数 $k$（$1\le k\le 60$）。 然后 $3\times n$ 行，一行一个整数 $w_i$ ($0 \leq w _ i \leq 1000$）， 表示贝西在 $i$ 个城市里拥有 $w_i$ 个支持者。

## 输出格式 输出有三组，第 $i$ 组输出 $k$ 行，表示第 $i$ 组的 $k$ 个城市编号。可能会有多组解，输出任意一组即可。 

## 样例 #1 

### 样例输入 #1 

2 

510 

500 

500 

670 

400 

310

### 样例输出 #1 

1 

2 

3 

6 

5 

4 

## 样例解释

第一组城市为城市 $1$ 和城市 $2$，贝西的支持者数量为 $510+500=1010，1010>2*1000/2$。

第二组城市为城市 $3$ 和城市 $6$，贝西的支持者数量为 $500+310=810，810<2*1000/2$。

第三组城市为城市 $5$ 和城市 $4$，贝西的支持者数量为 $400+670=1070，1070>2*1000/2$。

第一和第三两组城市中，支持贝西的人总数严格大于该组城市总选民数的一半， 贝西可以被选举为州长。 

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=200;
struct node{int x, id;} a[N];
bool cmp(node n1, node n2){
	return n1.x<n2.x;
}
int main(){
	int k; scanf("%d", &k); 
	int n=3*k;
	for(int i=1; i<=n; i++){
		scanf("%d", &a[i].x);
		a[i].id=i;
	}
	sort(a+1, a+n+1, cmp); 
	for(int i=1; i<=k; i++) printf("%d\n", a[i].id);
random_device rd;
mt19937 rng(rd());
while(1){
	int sum=0&#44; res=0&#44; t=k*500;
	for(int i=k+1; i&lt;=2*k; i++) sum+=a[i].x;
	res+=(sum&gt;t); sum=0;
	for(int i=2*k+1; i&lt;=n; i++) sum+=a[i].x;
	res+=(sum&gt;t); sum=0;
	if(res==2){
		for(int i=k+1; i&lt;=n; i++) printf("%d\n"&#44; a[i].id);
		break;
	}
	shuffle(a+k+2&#44; a+n+1&#44; rng);
}
return 0;

}

</p>