P1248 加工生产调度 题解

· · 个人记录

这里提供一篇纯退火的题解。

题意不多赘述，本题需要输出最短的加工时间和加工顺序，有 SPJ .

因为我五分钟之内没有头绪，所以考虑随机化算法。

考虑猴子排序，每次随机打乱整个序列，每次计算按照打乱后的序列计算加工时间，多次打乱，就有可能找到最优解。

如果每次用 STL 打乱整个数列复杂度过高，可以退而求次之，每次打乱两项，就是随机交换两项。

具体代码如下

void gswap(int x,int y){
    swap(a[x],a[y]);
    swap(b[x],b[y]);
    swap(id[x],id[y]);
}

void random_swap(){
    x=rnd(n),y=rnd(n);
    gswap(x,y);
    fcnew=count();
}

值得注意的是，退火算法还要随机地接受一些较劣解。因为可能最优解要通过这些较劣解得到。

完整代码如下：

int rnd(int x){
    if(x==0) return 0;
    return (rand())%x+1;
}

ll count(){
    ll res=0,tline=0;
    for(int i=1;i<=n;i++){
        tline+=a[i];
        res=max(res,tline)+b[i];
    }
    return res;
}

void gswap(int x,int y){
    swap(a[x],a[y]);
    swap(b[x],b[y]);
    swap(id[x],id[y]);
}

void mnth(){
    int x,y;
    ll fcold,fcnew,da;
    ll t;
    double delta;
    while((db)clock()/CLOCKS_PER_SEC<0.97){
        t=clock();
        fcold=count();
        x=rnd(n),y=rnd(n);
        gswap(x,y);
        fcnew=count();
        delta=fcnew-fcold;
        ans=min(ans,min(fcold,fcnew));
        if(delta<0||exp(-(delta)/t)>=rand()%32768) continue;
        else gswap(x,y);
    }
}