CF1355E Restorer Distance

模拟退火大法好

正解是三分，但是我不会写，还不想学。

众所周知，模拟退火算法可以使用O(?)的复杂度解决多峰函数最值的问题。因此这个题目依然可以使用模拟退火来解决。

不会这个算法的同学建议先去学习一下模拟退火算法入门，已经会的同学听我细细道来。

一、预处理

首先，我们需要进行预处理，降低退火过程中产生新解的复杂度。

对于输入的墙的高度a[i]我们可以先进行排序，并且求出前缀和sum[i]。

for(int i=1;i<=n;i++){
    cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
    sum[i]=sum[i-1]+a[i];
}

当我们每次产生一个新的砖块高度 x 时，我们需要快速计算出所需的代价。这时，我们可以先对排序过的a[i]二分查找新的高度 pos。

在这个新高度之前的墙需要抬高的总高度= x*pos-sum[pos]

在这个新高度之后的墙需要降低的总高度= (sum[n]-sum[pos])-x*(n-pos)

之后，如果M>A+R 那么我们只使用前两种操作；如果M≤A+R那么我们先尽可能进行M操作余下的分别计算。

int cal(int x){//假定墙的高度为x
    fans=0;//fans代表总共花费的代价
    pos=lower_bound(a+1,a+n+1,x)-a;//二分查找抬高与下降的平衡点
    pos--;
    xx=abs(x*pos-sum[pos]);
    yy=abs((sum[n]-sum[pos])-x*(n-pos));//计算抬高高度和下降高度
    if(M>A+R){//不使用M操作
        fans=A*xx+R*yy;
    }
    else{//优先使用M操作
        fans=min(xx,yy)*M;
        if(xx>yy){
            fans+=A*(xx-yy);
        }
        else{
            fans+=R*(yy-xx);
        }
    }
    return fans;
}

综上，我们优化单次计算约为O(log n)级别的时间复杂度，这为进行尽可能多次的模拟退火提供了充裕的时间。

二、模拟退火

通过 随机数×温度 产生一个新的最终墙面高度，如果该高度对应的答案严格小于已有答案，则采用之；反之，则以一定概率接受非最优解

void SA(){
    double T=1926087;//初始温度
    int x=0;//最终墙面高度
    while(T>1e-14){
        int new_x=x-(rand()*2-RAND_MAX)*T;//给出一个新的墙面高度
        if(new_x<0) continue;//注意，墙面高度不可以是负数
        int new_ans=cal(new_x);//计算开销
        int dE=new_ans-ans;
        if(dE<0){//优于已有解，接受之
            x=new_x;
            ans=new_ans;
        }
        else if(exp(-dE/T)*RAND_MAX>rand()){//一定概率接受非最优解
            x=new_x;
        }
        T*=0.99993;//降温系数
    }
}

关于参数问题，引用一下M_sea在洛谷日报的叙述：

Q：答案不是最优的怎么办？

A：有以下几种方法：调大 \Delta、调整 T_0和 T_k，以及多跑几遍SA。

当您的程序跑的比较快时，可以选择多跑几遍SA，或者调大 \Delta，从而增大得到最优解的概率。

T_0和 T_k的值需要根据值域对应调整，从而保证每次随机出的变化幅度不会跑太远。

Q：还是跑不出最优解怎么办？

A：那可能是您太非了。尝试更换随机数种子，或者 srand(rand())，总之，总有可能跑出正解。

Q：我是非酋，交了两页也没有用模拟退火AC，怎么办？

A：您还是选择打正解吧。

完整代码如下：

//XCPC RP++
#include<bits/stdc++.h>
#define int long long//注意开long long
using namespace std;
int n,A,R,M;
int a[100100],sum[100100];
int pos;
int xx,yy;
int fans;
int ans=1e18;
int cal(int x){
    fans=0;
    pos=lower_bound(a+1,a+n+1,x)-a;
    pos--;
    xx=abs(x*pos-sum[pos]);
    yy=abs((sum[n]-sum[pos])-x*(n-pos));
    if(M>A+R){
        fans=A*xx+R*yy;
    }
    else{
        fans=min(xx,yy)*M;
        if(xx>yy){
            fans+=A*(xx-yy);
        }
        else{
            fans+=R*(yy-xx);
        }
    }
    return fans;
}
void SA(){
    double T=1926087;
    int x=0;
    while(T>1e-14){
        int new_x=x-(rand()*2-RAND_MAX)*T;
        if(new_x<0) continue;
        int new_ans=cal(new_x);
        int dE=new_ans-ans;
        if(dE<0){
            x=new_x;
            ans=new_ans;
        }
        else if(exp(-dE/T)*RAND_MAX>rand()){
            x=new_x;
        }
        T*=0.99993;
    }
}
signed main(){
    srand(time(0));
    cin>>n>>A>>R>>M;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    SA();
    SA();
    SA();
    cout<<ans<<endl;
    return 0;
}