POJ 2454ランダム化+欲張り
1666 ワード
人品をテストする
TLEは何度も、配列が小さくなったことを知り、3を乗じて、自分の人柄がどうしてこんなに悪いのかと思った.
TLEは何度も、配列が小さくなったことを知り、3を乗じて、自分の人柄がどうしてこんなに悪いのかと思った.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>
#include <ctime>
#include <vector>
#include <string>
using namespace std;
int n;
int ans1[66],ans2[66],ans3[66];
int a[66*3],b[66*3];
bool cmp(int left,int right)
{
return a[left]<a[right];
}
int main ()
{
scanf("%d",&n);
for(int i=0;i<3*n;++i)
{
scanf("%d",&a[i]);
b[i]=i;
}
sort(b,b+3*n,cmp);
int res1=0,res2=0,res3=0;
for(int i=0;i<n;++i)
{
ans1[i]=b[i];
res1+=a[b[i]];
}
for(int i=n;i<3*n;++i)
{
if((i-n)&1)
{
ans3[(i-n)/2]=b[i];
res3+=a[b[i]];
}
else
{
ans2[(i-n)/2]=b[i];
res2+=a[b[i]];
}
}
int r=n*500;
for(int i=1;;++i)
{
/* if(i%10==0)
{
srand(time(0));
}*/
int p2=rand()%n;
int p3=rand()%n;
res2=res2+a[ans3[p3]]-a[ans2[p2]];
res3=res3+a[ans2[p2]]-a[ans3[p3]];
swap(ans2[p2],ans3[p3]);
if(res2>r && res3>r)
break;
}
sort(ans1,ans1+n);
sort(ans2,ans2+n);
sort(ans3,ans3+n);
for(int i=0;i<n;++i)
printf("%d
",ans1[i]+1);
for(int i=0;i<n;++i)
printf("%d
",ans2[i]+1);
for(int i=0;i<n;++i)
printf("%d
",ans3[i]+1);
return 0;
}