题目
在二维平面中有 \(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个,且不重叠,使得选中的数之和最小
//贪心