牛客25461 双喷泉浇花难题 如何用算法快速找到最优解
https://dajuwangluo.cn/zb_users/upload/2025/06/202506031748938350503930.jpg问题理解我们需要为两个喷泉确定最小的工作半径，使得：
[*]花坛中所有花都被浇灌到
[*]喷泉工作半径的平方和(r1² + r2²)最小
算法步骤详解
[*]输入处理：读取花朵和喷泉坐标
[*]距离计算：预处理每朵花到两个喷泉的距离平方
[*]排序优化：按到第一个喷泉的距离排序
[*]逆向扫描：维护第二个喷泉需要的最大半径
[*]结果计算：比较所有可能分割方案
完整代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Flower {
long long d1, d2; // 到两个喷泉的距离平方
};
int main() {
int n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
vector<Flower> flowers(n);
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
// 计算到两个喷泉的距离平方（避免浮点运算）
long long dx1 = x - x1, dy1 = y - y1;
long long dx2 = x - x2, dy2 = y - y2;
flowers.d1 = dx1*dx1 + dy1*dy1;
flowers.d2 = dx2*dx2 + dy2*dy2;
}
// 预处理：按d1升序排序
sort(flowers.begin(), flowers.end(),
[](const Flower& a, const Flower& b) {
return a.d1 < b.d1;
});
// 预处理后缀最大值数组
vector<long long> suffix_max(n+1, 0);
for (int i = n-1; i >= 0; --i) {
suffix_max = max(flowers.d2, suffix_max);
}
long long min_sum = suffix_max; // 初始化为全部由喷泉2覆盖的情况
// 遍历所有可能的分割点
for (int i = 0; i < n; ++i) {
long long current_sum = flowers.d1 + suffix_max;
min_sum = min(min_sum, current_sum);
}
cout << min_sum << endl;
return 0;
}
原文：牛客25461 双喷泉浇花难题 如何用算法找到最优解 从几何到优化的完美解法
页:
[1]