P3819 题解

· · 题解

这是一篇模拟退火的题解。

原题

题目描述

给出一条长 L 米的道路，道路上的坐标范围从 0 到 L，路上有 N 座房子，第 i 座房子建在坐标为 x_i 的地方，其中住了 r_i 人。

要求在这条路上找一个整数点，求每个居民从家到这个点的距离的总和最短，求这个最小值。

数据范围

--- ## Solution 容易得到，如果我们把 $x_0$ 点设为公交站，那么答案就表示为： $\min(\large\sum_{i=1}^{n}r_i |x_0-x_i|)

我们找到这个最小值点还是有很多方法的……

诶，暴力一点，直接模拟退火吧。

（不会模拟退火出门右转）

注意ans初值和long long，还有一些细节看代码吧。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int x,w;
};
node p[100010]; 
int l,n,ans=1e18,ansx;
int calc(int x)//计算答案
{
    int now=0;
    for(int i=1;i<=n;i++) now+=abs(x-p[i].x)*p[i].w;
    return now;
}
void sa()//板子
{
    double st=100,ed=1e-17,delta=0.975;//最喜欢0.975
    for(double t=st;t>=ed;t*=delta)
    {
        int x=ansx+(rand()*2-RAND_MAX)*t;
        int sum=calc(x);
        int del=sum-ans;
        if(del<0) ans=sum,ansx=x;//优则更新
        else if(exp(-del/t)*RAND_MAX>rand()) ansx=x;//不优有一定概率更新
    }
}
signed main()
{
    //玄学 
    srand(rand());
    srand(rand());
    cin>>l>>n;
    for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].w;
    int num=3;//总要跑几次 
    while(num--) sa();
    cout<<ans;
}