POJ2454 Jersey Politics
何でもいいから解を一つ求めればいいので、適当に山登り&登りきれなかったらrandom_shuffleで適当に書く。通る。(多分嘘解法じゃないはず)
K<=60をK<=20だと思っていて半分全列挙書いて配列外参照でREしてたのは内緒。
#include<stdio.h> #include<vector> #include<algorithm> #include<stdlib.h> using namespace std; typedef pair<int,int>pii; int main() { int num; scanf("%d",&num); vector<pii>vec; for(int i=0;i<3*num;i++) { int zan; scanf("%d",&zan); vec.push_back(make_pair(zan,i+1)); } sort(vec.begin(),vec.end()); reverse(vec.begin(),vec.end()); for(;;) { vector<int>a,b; int asum=0,bsum=0; for(int i=0;i<num;i++) { a.push_back(i); asum+=vec[i].first; } for(int j=0;j<num;j++) { b.push_back(j+num); bsum+=vec[j+num].first; } int han=0; for(;;) { if(asum>num*500&&bsum>num*500) { for(int i=0;i<num;i++) { printf("%d\n",vec[a[i]].second); } for(int i=0;i<num;i++) { printf("%d\n",vec[b[i]].second); } for(int i=0;i<num;i++) { printf("%d\n",vec[i+num+num].second); } return 0; } int mini=10000000; int sa,sb; for(int i=0;i<num;i++) { for(int j=0;j<num;j++) { if(mini>abs((asum-a[i]-a[i]+b[j]+b[j]-bsum))) { sa=i; sb=j; } } } if(mini==10000000) { han=1; } if(han==1) { random_shuffle(vec.begin(),vec.begin()+2*num); break; } asum-=a[sa]; bsum-=b[sb]; asum+=b[sb]; bsum+=a[sa]; swap(a[sa],b[sb]); } } }