牛客25461 双喷泉浇花难题 如何用算法找到最优解 从几何到优化的完美解法

问题理解

我们需要为两个喷泉确定最小的工作半径，使得：

1. 花坛中所有花都被浇灌到

2. 喷泉工作半径的平方和(r1² + r2²)最小

关键思路

1. ‌距离计算‌：对每朵花计算到两个喷泉的欧几里得距离平方

2. ‌排序处理‌：按到第一个喷泉的距离排序

3. ‌分割点搜索‌：从后往前寻找最优分割点，使得：

• 前i朵花由第一个喷泉覆盖

• 剩余花朵由第二个喷泉覆盖

4. ‌特殊情况处理‌：考虑全部由一个喷泉覆盖的情况

算法步骤详解

1. ‌输入处理‌：读取花朵和喷泉坐标

2. ‌距离计算‌：预处理每朵花到两个喷泉的距离平方

3. ‌排序优化‌：按到第一个喷泉的距离排序

4. ‌逆向扫描‌：维护第二个喷泉需要的最大半径

5. ‌结果计算‌：比较所有可能分割方案

完整代码

#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[i].d1 = dx1*dx1 + dy1*dy1;
        flowers[i].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[i] = max(flowers[i].d2, suffix_max[i+1]);
    }
    
    long long min_sum = suffix_max[0]; // 初始化为全部由喷泉2覆盖的情况
    
    // 遍历所有可能的分割点
    for (int i = 0; i < n; ++i) {
        long long current_sum = flowers[i].d1 + suffix_max[i+1];
        min_sum = min(min_sum, current_sum);
    }
    
    cout << min_sum << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(n log n) 主要来自排序

• 空间复杂度：O(n) 存储花朵距离信息

学习建议

1. 理解欧几里得距离的计算

2. 掌握贪心算法的应用场景

3. 练习排序和逆向扫描技巧

4. 尝试修改算法处理三个喷泉的情况

扩展思考

1. 如果喷泉位置也可调整，如何解决？

2. 考虑三维空间中的类似问题

3. 引入喷泉工作成本函数更复杂的情况

4. 动态增加/删除花朵的情况处理