POJ 2454ランダム化+欲張り

1666 ワード

人品をテストする
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; }