Sweets Eating

分析

一个贪心加找规律的题目，关键在于这个规律。
先考虑i和i-1之间多了什么，其实就相当于再i-1的序列的最开头插入了一个a[i]，对于i-1个数集体后移，其中只有离i-m+1有m个单位距离的数对解有影响，因为它们的天数改变了，那么ans[i]=ans[i-1]+a[i]+sum[i];sum[i]表示前面说的那些数的和，sum[i]与sum[i-m]之间有关系：sum[i]=sum[i-m]+a[i-m]，那么我们可以先预处理，这样就可以过了。

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <iostream>
using namespace std;
#define ll long long
int n, m;
int a[200005];
ll ans = 0;
ll sum[200005];
int main() {
scanf_s("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf_s("%d", &a[i]);
}
sort(a + 1, a + n + 1);
for (int i = 1+m; i <= n; i++)
{
sum[i] += sum[i-m]+a[i-m];
}
for (int i = 1; i <= n; i++) {
ans += a[i];
ans += sum[i];
cout << ans << " ";
}
return 0;
}

最后

以上就是俊秀狗为你收集整理的Sweets Eating的全部内容，希望文章能够帮你解决Sweets Eating所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。