注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2336(hnoi 2011) 任务调度  

2013-02-16 23:23:26|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

输出max{sigma{a[i]},sigma{b[i]}}有60分哟

 

其实这是个随机算法……

我用的是盲人爬山……

就是先对于3号任务暴力枚举他现在哪里弄,然后贪心一种方案,之后对方案进行若干次调整,如果更优就选择这个新方案。

具体看程序吧

 

当我好不容易好不容易调对了一交……

无限RE了

问vfleaking

bzoj上不能用srand(time(0))……

于是我一怒之下就直接rand了

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 25
using namespace std;
struct Task
{
    int flag,timea,timeb;
}task[MAXN],A[MAXN],B[MAXN],tempA[MAXN],tempB[MAXN],t1[MAXN],t2[MAXN];
bool cmp_to_B(const Task &a,const Task &b){  return a.timea>b.timea||(a.timea==b.timea&&a.timeb<b.timeb);  }
bool cmp_to_A(const Task &a,const Task &b){  return a.timeb>b.timeb||(a.timeb==b.timeb&&a.timea<b.timea);  }
int n,sA,sB,num[MAXN],tot,ans=1<<30;
void work()
{
    sort(A+1,A+sA+1,cmp_to_A);
    sort(B+1,B+sB+1,cmp_to_B);
    int ta=0,tb=0;
    for(int i=1;i<=sA;i++)
        ta+=A[i].timea;
    for(int i=1;i<=sB;i++)
        tb+=B[i].timeb;
    int t1=ta,t2=tb,temp,Minans=1<<30;
    for(int i=1;i<=2000;i++)
    {
        ta=t1,tb=t2;
        for(int j=1;j<=sA;j++)
            tempA[j]=A[j];
        for(int j=1;j<=sB;j++)
            tempB[j]=B[j];
        if(sA)  swap(A[rand()%sA+1],A[rand()%sA+1]);
        if(sB)  swap(B[rand()%sB+1],B[rand()%sB+1]);
        temp=0;
        for(int j=1;j<=sA;j++)
            temp+=A[j].timea,tb=max(tb,temp)+A[j].timeb;
        temp=0;
        for(int j=1;j<=sB;j++)
            temp+=B[j].timeb,ta=max(ta,temp)+B[j].timea;
        temp=max(ta,tb);
        if(temp>=Minans)
        {
            for(int j=1;j<=sA;j++)
                A[j]=tempA[j];
            for(int j=1;j<=sB;j++)
                B[j]=tempB[j];
        }
        Minans=min(Minans,temp),ans=min(ans,temp);
    }
}
void DFS(int p)
{
    if(p>tot)
    {
        for(int i=1;i<=sA;i++)
            t1[i]=A[i];
        for(int i=1;i<=sB;i++)
            t2[i]=B[i];
        work();
        for(int i=1;i<=sA;i++)
            A[i]=t1[i];
        for(int i=1;i<=sB;i++)
            B[i]=t2[i];
        return ;
    }
    A[++sA]=task[num[p]];
    if(rand()%32768<=25000)  DFS(p+1);
    sA--;
    B[++sB]=task[num[p]];
    if(rand()%32768<=25000)  DFS(p+1);
    sB--;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&task[i].flag,&task[i].timea,&task[i].timeb);
        if(task[i].flag==1)  A[++sA]=task[i];
        if(task[i].flag==2)  B[++sB]=task[i];
        if(task[i].flag==3)  num[++tot]=i;
    }
    DFS(1);
    printf("%d\n",ans);
    return 0;
}


  评论这张
 
阅读(604)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017