现在的位置: 首页 > 综合 > 正文

POJ 2454 随机化+贪心

2014年10月17日 ⁄ 综合 ⁄ 共 992字 ⁄ 字号 评论关闭

测试人品

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\n",ans1[i]+1);
    for(int i=0;i<n;++i)
        printf("%d\n",ans2[i]+1);
        for(int i=0;i<n;++i)
        printf("%d\n",ans3[i]+1);
    return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.