牛客25461题解析：动态规划+后缀数组解法

19339201706

一、题目解读

牛客25461题要求计算一个花园中n朵花到两个喷泉的最小距离平方和。用户需输入喷泉坐标(x1,y1)和(x2,y2)，以及n朵花的坐标(x,y)，通过合理分配每朵花到两个喷泉的距离，使总距离平方和最小。题目核心在于如何高效划分花与喷泉的归属，降低计算复杂度。

二、解题思路

采用“预处理排序+后缀最大值”的动态规划策略：

1. 距离平方计算：为避免浮点数误差，直接使用点到喷泉距离的平方（dx²+dy²）。

2. 优化关键：将花按到喷泉1的距离d1升序排序，使分割点左侧的花固定归属喷泉1，右侧花归属喷泉2。

3. 后缀数组：预处理后缀最大值数组，存储每个位置右侧花到喷泉2的最小距离平方和。

4. 遍历分割：枚举每个分割点，左侧总和为当前花的d1，右侧总和取自后缀最大值，动态更新最小和。

三、解题步骤

1. 输入处理：读取n、喷泉坐标及花朵坐标，计算每朵花的距离平方存入Flower结构。

2. 预处理排序：按d1对Flower数组升序排序，确保分割点左侧d1递增。

3. 构建后缀最大值数组：从右向左遍历，维护后缀中d2的最大值，形成后缀数组。

4. 动态求解：遍历分割点i，计算当前花d1+后缀数组[i+1]的和，更新全局最小值。

5. 输出结果：打印最小总距离平方和。

四、代码及注释

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. }

复制代码

五、总结

本解法巧妙结合排序与动态规划思想，通过预处理将二维决策转化为线性遍历，时间复杂度降至O(nlogn+O(n))=O(nlogn)。后缀最大值数组的应用避免了重复计算右侧距离和，显著提升了效率。对于类似需要划分区域并优化子区间的问题，该思路具备较强参考价值。后续可进一步探索空间优化或并行计算的可能。

链接：动态规划