题解 | 小红的圆移动

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 结构体存储每个圆的核心信息
struct C {
    long double x;      // 圆心x坐标
    long double y;      // 圆心y坐标
    long double r;      // 圆半径
    long double area;   // 圆的面积
    long double p = 1e100L;  // 圆需要移动的代价（初始化为极大值，未满足条件的圆保持极大值）
};

const ll N = 1e5 + 5;   // 数组最大容量（适配题目数据范围）
// 圆周率（long double高精度版本）
const long double pi = 3.14159265358979324L;
C a[N];  // 存储所有圆的数组

int main() {
    ll n, k;
    // 读取圆的总数n，以及最多允许保留的、无需移动的圆的数量k
    scanf("%lld%lld", &n, &k);
    ll cnt = 0;  // 统计：需要移动的圆的数量（覆盖原点的圆需要移动）
    
    // 遍历每个圆，计算核心参数并判断是否需要移动
    for (ll i = 1; i <= n; i++) {
        // 读取第i个圆的圆心坐标和半径
        scanf("%Lf %Lf %Lf", &a[i].x, &a[i].y, &a[i].r);
        // 计算圆的面积（π*r²，用乘法代替pow避免精度损失）
        a[i].area = pi * a[i].r * a[i].r;
        
        // 核心判断：圆是否覆盖原点（原点到圆心的距离 < 圆半径）
        // sqrtl计算long double高精度的平方根，避免pow(...,0.5)的精度损失
        if (a[i].r > sqrtl(a[i].x * a[i].x + a[i].y * a[i].y)) {
            // 计算移动代价p：(半径 - 原点到圆心的距离) * 圆面积
            // 含义：将圆移动到刚好不覆盖原点所需的"代价"，代价越小越优先选择移动
            a[i].p = (a[i].r - sqrtl(a[i].x * a[i].x + a[i].y * a[i].y)) * a[i].area;
            cnt++;  // 该圆需要移动，计数+1
        }
        // 不满足条件的圆：p保持1e100L（极大值），无需移动，cnt不增加
    }
    
    // 边界条件：需要移动的圆数量 <= 允许保留的数量k → 无需移动任何圆，总代价为0
    if (cnt <= k) {
        printf("0.0000000");
        return 0;
    }
    
    long double sump = 0;  // 累加需要移动的圆的总代价
    // 贪心策略核心：按移动代价p从小到大排序
    // 理由：要最小化总移动代价，优先选择代价最小的圆进行移动
    sort(a + 1, a + n + 1, [](C a, C b) {
        return a.p < b.p;
        });
    
    // 遍历排序后的圆，累加前(cnt-k)个最小代价的圆的总代价
    for (ll i = 1; i <= n; i++) {
        // 当需要移动的圆数量减少到k个时，停止并输出总代价
        if (cnt <= k) {
            printf("%.7Lf", sump);
            return 0;
        }
        sump += a[i].p;  // 累加当前最小代价的圆的移动代价
        cnt--;           // 已处理一个需要移动的圆，计数减1
    }
    return 0;
}