题目

在二维平面中有 \(n\) 只老鼠，有 \(A,B\) 两个洞，洞 \(A\) 的容量是 \(k\)，洞 \(B\) 的容量是 \(n-k\)。汤姆来了，每只老鼠都要钻进洞里，给出洞 \(A,B\) 和每只老鼠的坐标，安排老鼠进洞使老鼠进洞总路程最短。\(1\leq n，k\leq1e5,1\leq坐标值\leq1e9\)
允许误差 \(1e-5\)

分析

因为给定了点坐标，所以每点到a,b的距离都是固定的，可以先求出。
那么就转化为该问题：
两个长度为 \(n\) 的数组 \(a\) 和 \(b\)，\(a\) 中选 \(k\) 个数，\(b\) 中选 \(n-k\) 个数且两数组中选的数下标必须不同。求选出的 \(n\) 个数之和最小。\((n,k\leq 1e5)\)
策略：贪心选取。
只需先全选 \(b\) 然后再把最小的 \(k\) 个 \(a_i-b_i\) 加上即可

Code

#include <bits/stdc++.h>
#define db double

using namespace std;
const int N = 1e5 + 5;
int n, k, xa, ya, xb, yb;
db ans, e[N];

db count (int x1, int y1, int x2, int y2) {
    return sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main () {
    scanf ("%d%d%d%d%d%d", &n, &k, &xa, &ya, &xb, &yb);
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf ("%d%d", &x, &y);
        db disa = count (x, y, xa, ya), disb = count (x, y, xb, yb);
        e[i] = disa - disb;
        ans += disb;
    }
    sort (e + 1, e + n + 1);
    for (int i = 1; i <= k; i++)    ans += e[i];
    cout << fixed << setprecision (6) << ans << endl;
}

/*
在二维平面中有n只老鼠，有A,B两个洞，洞A的容量是k，洞B的容量是n-k，
汤姆来了，每只老鼠都要钻进洞里，给出洞A,B和每只老鼠的坐标，
安排老鼠进洞使老鼠进洞总路程最短。1<=n，k<=1e5,1<=坐标值<=1e9
允许误差1e-5
*/

//等价于两个数组sa,sb
//sa中选k个, sb中选n-k个,且不重叠,使得选中的数之和最小

//贪心