疑问
查看原帖
疑问
560516
喵仔牛奶楼主2022/10/24 22:18

我把 sum[a[i]] += a[i] 写出 sum[i] += a[i] 都能过?

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
typedef long long ll;
ll n, m, t, a[N], cnt[N], sum[N], f[N];
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], cnt[a[i]] ++, sum[i] += a[i], t = max(t, a[i]);
	for (int i = 1; i < t + m; i ++)
		cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
	for (ll i = 0; i < t + m; i ++) {
		f[i] = cnt[i] * i - sum[i];
		for (int j = max(i - 2 * m + 1, 0ll); j <= i - m; j ++)
			f[i] = min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
	}
	cout << *min_element(f + t, f + t + m) << '\n';
	return 0;
}

2022/10/24 22:18
加载中...