P4360

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20010;
int n,w[N],d[N],sum[N],S,sw[N];
int ans;
double Rand(){return (double)rand()/RAND_MAX;}
int calc(int x,int y)
{
    if (x>y) swap(x,y);
    return S-(sw[x+1]-sw[y+1])*sum[y]-(sw[1]-sw[x+1])*sum[x];
}
void SA()
{
    int x=1;
    int y=2;
    int pre=calc(x,y);
    double T=1000.0;
    while (T>1e-7)
    {
        int nx=(x+(int)(T*(rand()*2-RAND_MAX))%n+n)%n+1;
        int ny=(y+(int)(T*(rand()*2-RAND_MAX))%n+n)%n+1;
        int nw=calc(nx,ny);
        if (nw<pre)
        {
            x=nx,y=ny;
            pre=nw;
        }
        else if (exp(1.0*(pre-nw)/T)>Rand())
        {
            //printf("%.2lf %.2lf\n",exp(1.0*(pre-nw)/T),1.0*mt()/((1ll<<32)+1));
            x=nx,y=ny;
            pre=nw;
        }
        T*=0.9985;
    }
    ans=min(ans,pre);
}
signed main()
{
    srand(time(0));
    scanf("%lld",&n);
    for (int i=1;i<=n;i++)
        scanf("%lld %lld",&w[i],&d[i]);
    for (int i=n;i>0;i--)
    {
        sum[i]=sum[i+1]+d[i];
        ans+=sum[i]*w[i];
        S+=sum[i]*w[i];
        sw[i]=sw[i+1]+w[i];
    }
    while ((double)clock()/CLOCKS_PER_SEC<0.99) SA();
    printf("%lld\n",ans);
    //printf("%d",calc(3,6));
    //printf("%.2lf",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

搞不懂为什么 T 的下界要设到 10−7，就算 Δ 最小取 1，当 T 取到 1e−7 的时候 exp 就是 $\frac{1}{e^{10^7}}$，真的需要这么小的概率去退火吗？但是我如果把T下界改成 1e-6 又会wa很多