38 lines
1.3 KiB
C++
38 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
// 通过了 10/20个数据
|
||
const int N = 4000010;
|
||
const int INF = 0x3f3f3f3f;
|
||
int f[N], cnt[N], sum[N];
|
||
int n, m; // 等车人数和摆渡车往返一趟的时间
|
||
int T; // T表示最后一个同学到达车站的时间
|
||
|
||
int main() {
|
||
cin >> n >> m;
|
||
for (int i = 1; i <= n; i++) {
|
||
int t; // 每个同学到达车站的时刻
|
||
cin >> t;
|
||
T = max(T, t); // 最后一个同学到达车站的时间
|
||
cnt[t]++; // t时刻引发的到达车站的人数，可能是多人
|
||
sum[t] += t; // t时刻引发的等待时间和，可能是多人
|
||
}
|
||
|
||
// 注意，这里应计算到最后一同学可能等到的时间
|
||
for (int i = 1; i < T + m; i++) {
|
||
cnt[i] += cnt[i - 1]; // 求人数的前缀和
|
||
sum[i] += sum[i - 1]; // 求时间的前缀和
|
||
}
|
||
|
||
for (int i = 1; i < T + m; i++) {
|
||
f[i] = i * cnt[i] - sum[i]; // 特殊处理i<m的情况
|
||
for (int j = 0; j <= i - m; j++)
|
||
f[i] = min(f[i], (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]) + f[j]);
|
||
}
|
||
// 取右边界取的漂亮
|
||
int ans = INF;
|
||
for (int i = T; i < T + m; i++) ans = min(ans, f[i]);
|
||
cout << ans << endl;
|
||
return 0;
|
||
}
|