最优政府大楼选址｜加权中位数与模拟退火

T6 - 最优政府大楼选址-2

题目链接跳转：点击跳转

解题思路

本题有好多解决方法，可以使用带权中位数写 $N = 10^5$​，为了考虑到朴素的模拟退火算法，本题的数据范围被适当降低了。如果学过模拟退火算法做这道题就非常的简单，把模板的评估函数改成计算意向程度的函数即可。

时间复杂度

模拟退火算法的时间复杂度约为 $\Theta(k \times N)$。其中 $k$ 表示的是在模拟退火过程中计算举例的 F2 函数的调用次数。$N$ 表示数据规模。

代码实现

本题的 C++ 代码如下（模拟退火）：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <random>
using namespace std;

double n;
struct apart{
    double x, y;
} arr[10005];
double ei[10005];
double answ = 1e18, ansx, ansy;

double dis(double x1, double y1, double x2, double y2, int c){
    return (abs(x1 - x2) + abs(y1 - y2)) * ei[c];
}

double F2(double x, double y){
    double ans = 0;
    for (int i=1; i<=n; i++){
        ans += dis(x, y, arr[i].x, arr[i].y, i);
    }
    return ans;
}

void SA(){
    double T = 3000, cold = 0.999, range = 1e-20;
    answ = F2(ansx, ansy);
    while(T > range){
        double ex = ansx + (rand() * 2.0 - RAND_MAX) * T;
        double ey = ansy + (rand() * 2.0 - RAND_MAX) * T;
        double ea = F2(ex, ey);
        double dx = ea - answ;
        if (dx < 0){
            ansx = ex;
            ansy = ey;
            answ = ea;
        } else if (exp(-dx/T) * RAND_MAX > rand()){
            ansx = ex;
            ansy = ey;
        }
        T *= cold;
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++) cin >> ei[i];
    for (int i=1; i<=n; i++){
        cin >> arr[i].x >> arr[i].y;
        ansx += arr[i].x; ansy += arr[i].y;
    }
    ansx /= n; ansy /= n;
    for (int i=1; i<=1; i++) SA();
    printf("%.5lf\n", answ);
    return 0;
}

使用加权中位数算法的 C++ 代码：

#include <bits/stdc++.h>

constexpr double EPS = 1e-6;

double get_med(const std::vector<double> &a, const std::vector<int> &e) {
    int n = a.size();
    double lo = -1e3, hi = 1e3;
    auto f = [&](double x) {
        double sum = 0.0;
        for (int i = 0; i < n; ++i)
            sum += std::abs(x - a[i]) * e[i];
        return sum;
    };
    while (hi - lo > EPS) {
        double mid = (lo + hi) / 2;
        if (f(mid - EPS) > f(mid) and f(mid) > f(mid + EPS))
            lo = mid;
        else
            hi = mid;
    }
    return lo;
}

int main() {
    int n; std::cin >> n;
    std::vector<int> e(n);
    for (auto &x : e) std::cin >> x;
    std::vector<double> x(n), y(n);
    for (int i = 0; i < n; ++i)
        std::cin >> x[i] >> y[i];
    double ax = get_med(x, e), ay = get_med(y, e);
    double res = 0.0;
    for (int i = 0; i < n; ++i)
        res += (std::abs(ax - x[i]) + std::abs(ay - y[i])) * e[i];
    std::cout << std::setprecision(6) << std::fixed << res << '\n';
    return 0;
}