P1248 加工生产调度

P1248 加工生产调度 题解

标签：贪心 模拟退火（？）

刷贪心刷到的此题，想了半天终于研究明白了题解区大佬的贪心策略和细节，然后——

机房大佬鑫哥提示我，这题似乎不用贪心？

发现对于一个工作顺序，可以直接计算答案，也就是说，完全可以用模拟退火做！！！（而且好像没有题解这样写）

那么这题就和下面这题非常像

P3878 [TJOI2010] 分金币

（我的模拟退火初体验）

模拟退火具体算法这里不多阐述，可以到上面题的题解区里面看。

简单来说，就是更优的一定更新答案，不优的也有一定概率成为答案，然后不停交换看看是否更优。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans[1010],num[1010],a[1010],b[1010],Ans=1e10,sum;
void update()
{
    for(int i=1;i<=n;i++) ans[i]=num[i];
    Ans=sum;
}
int get()
{
    //模拟过程，这里其他题解也有类似写法
    int nowa=0,nowb=0;
    for(int i=1;i<=n;i++)
    {
        nowa+=a[num[i]];
        nowb=max(nowa,nowb);
        nowb+=b[num[i]];
    }
    return nowb;
}
void sa()//模拟退火
{
    double st=100,ed=1e-8,delta=0.9357;
    for(double t=st;t>ed;t*=delta)
    {
        int x=rand()%n+1,y=rand()%n+1;
        swap(num[x],num[y]);
        sum=get();
        int dt=sum-Ans;
        if(dt<0) update();
        else if(exp(-dt/t)<double(rand())/RAND_MAX) swap(num[x],num[y]);
    }
}
signed main()
{
    srand(rand());
    srand(rand());
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) num[i]=i;
    int cnt=500;
    while(cnt--) sa();
    cout<<Ans<<'\n';
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}