const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

function minCost() {
    let input = "";

    rl.on("line", (line) => {
        input += line + " ";
    });

    rl.on("close", () => {
        const data = input.trim().split(/\s+/).map(Number);
        let idx = 0;
        const n = data[idx++];
        const k = data[idx++];

        const costs = [];

        for (let i = 0; i < n; i++) {
            const x = data[idx++];
            const y = data[idx++];
            const r = data[idx++];

            // Calculate distance from origin to center
            const dist = Math.hypot(x, y);

            if (dist <= r) {
                // Circle contains origin
                // Cost to move it just outside: πr² * (r - dist)
                const cost = Math.PI * r * r * (r - dist);
                costs.push(cost);
            } else {
                // Already doesn't contain origin, cost 0
                costs.push(0.0);
            }
        }

        // Sort costs in ascending order
        costs.sort((a, b) => a - b);

        // We need to keep at most k circles containing origin
        // So we keep the k largest costs (don't move them), and move the rest
        // Sum the smallest (n - k) costs
        const totalCost = costs
            .slice(0, Math.max(0, costs.length - k))
            .reduce((sum, cost) => sum + cost, 0);

        // Print with sufficient precision
        console.log(totalCost.toPrecision(15));
    });
}

minCost();

解题思路分析

问题回顾

• 平面上有n个圆，每次操作可移动一个圆，代价为圆面积×移动距离
• 目标：使最终包含原点的圆数量≤k，求最小总代价

代码思路详解

1. 输入处理

javascriptApplyconst readline = require('readline');
const rl = readline.createInterface({ 
    input: process.stdin, 
    output: process.stdout 
});

// ...

rl.on('line', (line) => { 
    input += line + ' '; 
});

rl.on('close', () => { 
    const data = input.trim().split(/\s+/).map(Number); 
    // ...
});

• 使用Node.js的readline模块读取标准输入
• 将所有输入数据合并并转换为数字数组，方便后续处理

2. 核心成本计算

javascriptApplyfor (let i = 0; i < n; i++) { 
    const x = data[idx++]; 
    const y = data[idx++]; 
    const r = data[idx++]; 
    
    // Calculate distance from origin to center 
    const dist = Math.hypot(x, y); 
    
    if (dist <= r) {  // Circle contains origin 
        // Cost to move it just outside: πr² * (r - dist) 
        const cost = Math.PI * r * r * (r - dist); 
        costs.push(cost); 
    } else { 
        // Already doesn't contain origin, cost 0 
        costs.push(0.0); 
    } 
}

关键逻辑：

• 计算每个圆圆心到原点的距离dist
• 包含原点的圆：计算将其移出原点所需的最小代价移动距离：只需移动到刚好不包含原点的位置，即(r - dist)代价公式：面积 × 移动距离 = πr² × (r - dist)
• 不包含原点的圆：无需移动，代价为0

3. 最优策略选择

javascriptApply// Sort costs in ascending order 
costs.sort((a, b) => a - b); 

// We need to keep at most k circles containing origin 
// So we keep the k largest costs (don't move them), and move the rest 
// Sum the smallest (n - k) costs 
const totalCost = costs.slice(0, Math.max(0, costs.length - k)).reduce((sum, cost) => sum + cost, 0);

贪心策略：

• 将所有代价按升序排序
• 保留代价最高的k个圆（不移动它们），移动其余代价较低的圆因为移动代价高的圆会增加总代价，所以保留它们更划算
• 总代价：所有需要移动的圆的代价之和，即排序后前(costs.length - k)个最小代价的总和

4. 结果输出

javascriptApply// Print with sufficient precision 
console.log(totalCost.toPrecision(15));

• 使用toPrecision(15)确保输出足够的精度，满足题目要求的相对误差不超过10⁻⁶

算法复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(n)，用于存储所有圆的移动代价

核心洞察

• 移动圆的最优策略是尽可能保留那些移动代价高的圆，移动代价低的圆
• 对于每个包含原点的圆，最小移动距离是将其移动到刚好不包含原点的位置
• 不包含原点的圆无需移动，不产生代价

这种贪心策略确保了总代价最小化，是解决此类问题的高效方法。