首页 > 试题广场 >

小红的圆移动

[编程题]小红的圆移动

热度指数：1784 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

平面上有 $n$ 个圆，小红可以进行任意次操作，每次操作可以选择一个圆，将它向任意方向移动若干距离。该操作的代价为该圆面积乘以移动的距离。
小红希望最终包含原点的圆数量不超过 $k$ ，请你帮小红算出她操作的最小总代价。

输入描述:

第一行输入两个正整数，用空格隔开。
接下来的行，每行输入三个整数，代表第个圆的圆心是，半径是。

输出描述:

一个实数，代表操作的最小总代价。若你的输出和标准答案的相对误差不超过，则认为你的答案正确。

示例1

输入

2 1
0 0 1
0 0 2

输出

3.14159265358979324

说明

显然将小圆向任意方向移动距离1即可。

算法知识视频讲解

Python3

驴主

操作的代价和最小等价于不操作的代价和最大。用最小堆保留代价最大的 k 个操作，剩余的求和即可。

import heapq
from math import sqrt, pi

class Heap:
    def __init__(self, k) -> None:
        self.hp = []
        self.size = k 

    def push(self, x):
        if len(self.hp) < self.size:
            heapq.heappush(self.hp, x)
            return 0
        return heapq.heappushpop(self.hp, x)

n, k = map(int, input().strip().split())
ans = 0
hp = Heap(k)

for _ in range(n):
    x, y, r = map(int, input().strip().split())
    d = sqrt(x * x + y * y)
    if d >= r:
        continue 
    ans += hp.push((r - d) * r * r)
print(ans * pi)

# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠶⠟⠛⠛⠛⠛⠷⡶⠶⠿⠛⠷⠶⣦⣤⡀
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠶⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠶⣄
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢶⡀
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠫⠒⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢄⠀⠀⠀⠀⠉⢷⡀
# ⠀⠀⠀⠀⠀⠀⣠⡾⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠒⡀⠀⠀⠀⠙⣦
# ⠀⠀⠀⠀⣠⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢆⠀⠀⠀⠘⣧
# ⠀⠀⠀⣴⠁⠀⢀⠤⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠈⢿⡀
# ⠀⠀⡾⠀⣠⢾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡆⠀⠀⠀⠹⣆
# ⠀⢸⢁⠞⠀⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣿⠀⠀⠀⠀⠀⠀⢰⣿⠑⠢⣄⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠘⣆
# ⠀⠘⠃⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠠⠋⢀⢏⢿⠀⠀⠀⠀⠀⢀⣿⣌⣆⠀⠀⣏⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠈⠀⠀⢄⠀⠀⢹⡀
# ⠀⠀⠀⠀⢀⡇⠀⠀⠀⠀⠀⠀⢠⠀⠀⡟⠟⢞⣇⠀⠀⠀⠀⢿⠟⠀⠙⣆⠀⢹⢦⡀⠀⠘⠀⠀⠀⠀⠀⠀⣄⠀⠀⠀⢳⡀⠀⣇
# ⠀⠀⠀⣤⠋⠀⠀⠀⠀⠀⠀⢀⡿⡄⢸⠙⠀⠀⠻⣆⢠⣄⠀⠀⣧⠀⠀⠀⠛⢦⣷⠙⢶⣄⠀⠀⠀⠀⠀⠀⠹⡀⠀⢠⣼⠻⡀⡟
# ⢀⣴⠟⠀⠀⠀⣀⠞⠀⠀⠀⣼⢋⠈⠻⠀⢀⣪⡶⠀⠛⠃⠉⠛⠻⣬⣑⣀⣀⣀⣤⣶⣷⣸⠀⠀⠀⠀⠠⠀⠀⠙⣄⠀⣿⠀⠛
# ⠀⠉⠛⠛⡿⠁⠀⠀⣄⠀⠀⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⡿⠿⡿⠀⠀⠀⠀⠀⡾⠓⠶⠶⠋⠘⣦
# ⠀⠀⢀⠟⠀⠀⠀⣼⣿⣦⡀⠹⡀⠀⠙⠁⠀⠀⠒⠶⠒⠲⠤⠴⠀⠀⠀⠀⠁⠀⠀⠀⣾⠀⠀⠀⠀⠀⡾⠉⢷⣳⢄⠀⠀⠈⠳⣄
# ⠀⠀⡿⠀⠀⠀⣠⣿⣿⢿⣿⠉⠉⠎⢀⠀⡎⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠀⠃⢸⠀⣿⡤⣶⠁⠀⢠⣿⣿⠛⢀⣿⡇⡿⠶⣤⣤⣤⠟
# ⠀⠀⡇⠀⡴⢋⣼⠗⣉⢯⣿⣷⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠀⣀⣾⠉⠉⠀⣠⣿⣿⣧⣿
# ⠀⠀⠹⠟⠀⣧⡴⣻⠃⣾⣿⣿⣋⠛⢶⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣛⣿⣿⣍⣴⣭⣿⡻⣿⣿⣿⣿⣞⣦
# ⠀⠀⠀⠀⠀⣾⣿⠃⢰⣿⠟⠐⣿⢏⣿⣿⣝⣿⣿⣿⠿⠶⠶⠶⠶⠶⠶⣿⠟⣩⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣷⣿⣦⣤
# ⠀⠀⠀⠀⠀⠠⣧⡀⣿⠁⢀⠋⢠⠋⠀⠙⠀⠉⠁⠀⠀⠀⠀⠀⠀⣴⣻⣿⣿⠦⣠⠛⠋⠁⣿⣿⠋⠻⣿⣿⣿⠉⠛⠿⠿⠛⠋
# ⠀⠀⠀⠀⠀⠀⠀⠀⣿⣾⢻⢠⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⢸⣿⡿⣵⠛⠀⠀⠀⠀⠁⠀⠀⠀⣿⠟
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣏⡟⡟
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿

发表于 2025-12-26 00:48:59 回复(0)

C++

Reisentyan

我们将使用拉马努金瞪眼法解决这一题

注意到先判断每个圆是否包含原点再计算包含原点的每个圆操作代价之后给所有包含原点的圆根据权值排序再计算需要移动几个圆到原点外面用数组上遍历一遍记录答案后 printf 设置小数点后6位输出就可以了。

注意到，代码要写成这样：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const double PI = 3.14159265358979324;
int main() {
    int n,k;
    cin>>n>>k;
    vector<double>c;
    for(int i =1;i<=n;i++)
    {
        double x,y,r;
        cin>>x>>y>>r;
        if(r*r > x*x+y*y)
        {
             c.push_back((PI*r*r*r) - (PI*r*r *(sqrt(x*x+y*y))));
        }
    }
    auto cmp=[&](double a,double b)->bool {return a>b;};
    sort(c.begin(),c.end(),cmp);
    int now = c.size();
    double ans = 0;
    while(now>k)
    {
        ans+=c.back();
        c.pop_back();
        now--;
    };
    printf("%.10lf",ans);
}
/*
⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿
⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘
⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧
⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄
⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦
⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄
⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀
⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘
⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄
⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿
⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀
⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇
⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷
⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟
⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁
⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿
⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷
⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿
⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿
⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀
⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱
⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿
⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷
⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿
*/

编辑于 2025-12-26 00:32:37 回复(2)

LosTiangle

卡tm输入也是离谱了, 手搓getchar17ms, scanf 41ms , cin 127ms 什么东西

发表于 2025-12-26 17:46:45 回复(1)

Estrella_pi

没卡浮点数误差，不习惯了ᓚᘏᗢ。

发表于 2025-12-26 16:06:47 回复(0)

牛客776090373号

昨天出一个烂题今天一个烂题浪费时间鸟

发表于 2025-12-26 15:13:40 回复(0)

提交观点

问题信息

难度：

5条回答 6收藏 76浏览

小红的圆移动

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题