牛客25461题解析：动态规划+后缀数组解法
https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506081749375607843687.jpg
一、题目解读牛客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+后缀数组的和，更新全局最小值。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.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;
}
五、总结本解法巧妙结合排序与动态规划思想，通过预处理将二维决策转化为线性遍历，时间复杂度降至O(nlogn+O(n))=O(nlogn)。后缀最大值数组的应用避免了重复计算右侧距离和，显著提升了效率。对于类似需要划分区域并优化子区间的问题，该思路具备较强参考价值。后续可进一步探索空间优化或并行计算的可能。链接：动态规划
页:
[1]