牛客25461 双喷泉浇花难题 如何用算法快速找到最优解

19339201706

问题理解

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

• 花坛中所有花都被浇灌到
• 喷泉工作半径的平方和(r1² + r2²)最小
  
  

算法步骤详解

• ‌输入处理‌：读取花朵和喷泉坐标
• ‌距离计算‌：预处理每朵花到两个喷泉的距离平方
• ‌排序优化‌：按到第一个喷泉的距离排序
• ‌逆向扫描‌：维护第二个喷泉需要的最大半径
• ‌结果计算‌：比较所有可能分割方案
  
  

完整代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. struct Flower {
   
7.     long long d1, d2; // 到两个喷泉的距离平方
   
8. };
   
9. 
   
10. int main() {
    
11.     int n, x1, y1, x2, y2;
    
12.     cin >> n >> x1 >> y1 >> x2 >> y2;
    
13.    
    
14.     vector<Flower> flowers(n);
    
15.     for (int i = 0; i < n; ++i) {
    
16.         int x, y;
    
17.         cin >> x >> y;
    
18.         // 计算到两个喷泉的距离平方（避免浮点运算）
    
19.         long long dx1 = x - x1, dy1 = y - y1;
    
20.         long long dx2 = x - x2, dy2 = y - y2;
    
21.         flowers[i].d1 = dx1*dx1 + dy1*dy1;
    
22.         flowers[i].d2 = dx2*dx2 + dy2*dy2;
    
23.     }
    
24.    
    
25.     // 预处理：按d1升序排序
    
26.     sort(flowers.begin(), flowers.end(),
    
27.         [](const Flower& a, const Flower& b) {
    
28.             return a.d1 < b.d1;
    
29.         });
    
30.    
    
31.     // 预处理后缀最大值数组
    
32.     vector<long long> suffix_max(n+1, 0);
    
33.     for (int i = n-1; i >= 0; --i) {
    
34.         suffix_max[i] = max(flowers[i].d2, suffix_max[i+1]);
    
35.     }
    
36.    
    
37.     long long min_sum = suffix_max[0]; // 初始化为全部由喷泉2覆盖的情况
    
38.    
    
39.     // 遍历所有可能的分割点
    
40.     for (int i = 0; i < n; ++i) {
    
41.         long long current_sum = flowers[i].d1 + suffix_max[i+1];
    
42.         min_sum = min(min_sum, current_sum);
    
43.     }
    
44.    
    
45.     cout << min_sum << endl;
    
46.     return 0;
    
47. }

复制代码

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