POJ2454 Jersey Politics

随机化算法。

亲身试验贪心会T。

所以排序，然后在前2*k个数中随机交换。

祝大家新年快乐。

 1 #include<algorithm>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<iostream>
 6 using namespace std;
 7 int k,tmp,cnt1,cnt2;
 8 struct node
 9 {
10     int id,s;
11     bool operator<(const node &b)const{
12         return s>b.s;
13     }
14 }q[200];
15 int main()
16 {
17     scanf("%d",&k);
18     tmp=k*500;
19     for(int i=1;i<=k*3;++i)
20     {
21         q[i].id=i;scanf("%d",&q[i].s);
22     }
23     int cnt=0;
24     sort(q+1,q+1+3*k);
25     while(1)
26     {
27         cnt1=cnt2=0;
28         for(int i=1;i<=k;++i)
29         {
30             cnt1+=q[i].s;
31         }
32         for(int i=k+1;i<=k*2;++i)
33         {
34             cnt2+=q[i].s;
35         }
36         if(cnt1>tmp&&cnt2>tmp)
37         {
38             for(int i=1;i<=k*3;++i)
39             cout<<q[i].id<<endl;
40             return 0;
41         }
42         swap(q[rand()%k+1],q[rand()%k+k+1]);
43         cnt++;
44     }
45     return 0;
46 }