一、题目描述CSP-J 入门难度一条笔直公路上分布 n 个村庄各村庄按坐标 1、2、…、n 依次排列相邻村庄间距为 1。每个村庄有固定人口权值需在某一村庄建立快递站使得所有村庄的 “人口 × 到快递站距离” 之和最小输出该最小和。输入输出规范输入第一行输入 n村庄数量第二行输入 n 个整数代表各村庄人口权值村庄坐标与序号一致1~n。输出输出最小的加权距离和。输入输出样例5 13 4 12 20 40输出81样例说明快递站建在坐标 3 时加权距离和最小计算得总距离和为 81。数据规模1 ≤ n ≤ 100村庄人口权值为正整数适配 CSP-J 入门难度要求。二、解法一暴力枚举法CSP-J 初赛首选核心思路枚举每个村庄作为快递站位置计算该位置对应的加权距离和遍历所有位置后取最小值作为答案。该方法逻辑简单、代码简洁适合 CSP-J 初赛基础答题场景。完整代码标准 C可直接复制运行#include iostream #include cstdlib // 用于abs()函数 using namespace std; int main() { int n; cin n; int w[105]; // 存储各村庄人口权值 for (int i n; i) { cin w[i]; } int min_sum 1e9; // 初始化最小值为极大值 // 枚举每个位置作为快递站 for (int k n; k) { int current_sum 0; // 计算当前位置k的加权距离和 for (int i 1; n; i) { current_sum w[i] * abs(i - k); } // 更新最小距离和 if (current min_sum) { min_sum current_sum; } } cout endl; return 0; }算法分析时间复杂度 O (n²)n≤100 时无超时问题代码无复杂逻辑仅通过双重循环完成枚举与计算适配 CSP-J 初赛对基础算法的考察要求是初学者最易掌握的解法。三、解法二动态规划法CSP-J 复赛进阶核心思路利用前缀和优化计算通过状态转移推导各位置的加权距离和将时间复杂度优化至 O (n)适用于 n 更大的场景也是 CSP-J 复赛中考察的核心思路。关键定义前缀和数组 pre_sumpre_sum [i] 表示前 i 个村庄的人口总和即 pre_sum [i] w [1] w [2] … w [i]DP 数组 dp [i]表示快递站建在第 i 个村庄时所有村庄的加权距离和状态转移基于前一位置的 DP 值推导当前位置的 DP 值避免重复计算。状态转移公式设 dp [i] 为快递站在第 i 个村庄时的加权距离和则dp [i] dp [i-1] pre_sum [i-1] - (pre_sum [n] - pre_sum [i-1])推导逻辑当快递站从 i-1 移动到 i 时左侧 1~i-1 村庄的距离各增加 1总增加量为 pre_sum [i-1]右侧 i~n 村庄的距离各减少 1总减少量为 pre_sum [n] - pre_sum [i-1]两者叠加得到当前 dp [i]。完整代码标准 C可直接复制#include iostream using namespace std; const int MAXN 105; int w[MAXN], pre_sum[MAXN], dp[MAXN]; int n, sum_total 0; int main() { cin n; for (int i 1; i n; i) { cin w[i]; sum_total w[i]; pre_sum[i] pre_sum[i-1] w[i]; // 计算前缀和 } // 初始化dp[1]快递站在第1个村庄 dp[1] 0; for (int i 2 n; i) { dp[1] w[i] * (i - 1); } // 状态转移推导所有dp[i] for (int i n; i) { int left pre_sum[i-1]; int right sum_total - pre_sum[i-1]; dp[i] dp[i-1] left - right; } // 查找最小的dp值 int min_sum dp[1]; for (int i n; i) { if (dp[i] min_sum) { min_sum dp[i]; } min endl; return 0; }四、两种解法对比CSP-J 备赛重点解法类型时间复杂度代码难度适用场景暴力枚举法O(n²)低CSP-J 初赛、零基础入门、n≤100动态规划法O(n)中CSP-J 复赛、n 较大场景、锻炼 DP 思维