C++蓝桥杯代码.zip

#include <bits/stdc++.h> #define N 4000010 #define MAXINT 1e9 using namespace std; int f[N], cnt[N], sum[N]; int main() { int n, m, t, T = 0; // T表示最后一个同学到达车站的时间 cin >> n >> m; for(int i = 1; i <= n; i ++) { cin >> t; T = max(T, t); // 读入时要记录最后一个到达车站的时间 cnt[t] ++; // 初始记录 t 时刻到达车站的人数 sum[t] += t; // 初始记录 t 的数值和 } for(int i = 1; i < T + m; i ++) // i的循环区间为 [1, T + (m-1)] { cnt[i] += cnt[i - 1]; // 计算前缀和：cnt[i] 表示截止到 i 时刻之前到达车站人数总和为 cnt[i] sum[i] += sum[i - 1]; // 计算前缀和：sum[i] 表示截止到 i 时刻之前的所有点的数值和 } for(int i = 1; i < T + m; i ++) // i的循环区间为 [1, T + (m-1)] { // 由于在主循环中，j <= i - m，当 i < m 时无法执行。故先计算 i∈(0, m] 时的 f[i] （当i∈(0, m]时，j=0，f[0]=cnt[0]=sum[0]=0） f[i] = i * cnt[i] - sum[i]; // 核心代码 int k = max(0, i - 2 * m + 1); // i-2m＜ j 且 j不能为负数 for(int j = k; j <= i - m; j ++) f[i] = min(f[i], (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]) + f[j]); } int ans = MAXINT; for(int i = T; i < T + m; i ++) ans = min(ans, f[i]); cout << ans << endl; return 0; }