题目

Access Points

给定n个点坐标，编号1~n。让你重新安排这n个点坐标，满足编号小的横纵坐标均小于等于编号大的横纵坐标，同时让每个点偏移的距离平方和最小，输出最小值。

题解

显然，x和y坐标独立，可以分开处理。

问题变成一维问题。因为最终坐标要按照编号从小到大递增。编号连续的点肯定要么移动到同一个点，要么不动。当\(x_l,...,x_r\)移动到同一点\(d\)，代价为\(\sum\limits_{i=l}^{r}{(x_i-d)^2}\)。拆开得\((r-l+1)d^2-2d\sum\limits_{i=l}^r{x_i}+\sum\limits_{i=l}^r{x_i^2}\)。把\(d\)为未知量，极小值点为\(-\frac{-2d\sum\limits_{i=l}^r{x_i}}{2(r-l+1)}=\frac{\sum\limits_{i=l}^r{x_i}}{(r-l+1)}\)，即\(d\)取平均值时代价最小。

因此直接用单调栈维护平均值递增即可。

关键在于平均值处代价最小。

#include <bits/stdc++.h>

#define endl '\n'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N) 
typedef long long ll;

using namespace std;
/*-----------------------------------------------------------------*/

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f

const int N = 3e5 + 10;
const double eps = 1e-5;

int xpos[N], ypos[N];
typedef pair<double, int> PDI;

double sqr(double x) {
    return x * x;
}

double solve(int pos[], int n) {
    stack<PDI> st;
    for(int i = 1; i <= n; i++) {
        PDI cur = {pos[i], 1};
        while(!st.empty() && st.top().first > cur.first) {
            cur.first = cur.first * cur.second + st.top().first * st.top().second;
            cur.second += st.top().second;
            cur.first /= cur.second;
            st.pop();
        }
        st.push(cur);
    }
    double res = 0;
    int p = n;
    while(!st.empty()) {
        auto cur = st.top();
        st.pop();
        while(cur.second--) {
            res += sqr(cur.first - pos[p--]);
        }
    }
    return res;
}

int main() {
    IOS;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> xpos[i] >> ypos[i];
    }
    cout << seteps(10) << solve(xpos, n) + solve(ypos, n) << endl;
}