Codeforces 1253C Sweets Eating

思路：

1.按照贪心的思想，吃k个糖果一定吃从小到大前k个糖果，且ai大的放在前面吃，因为放在后面吃要翻倍；
2.在草稿上稍微画一下图就可以知道，从吃k个糖果到吃k+1个的过程中，我们需要加上a[k+1]+a[k+1-m*1]+a[k+1-m*2]+...+a[(k+1)%m]（这里的数组a[]是升序排序后的），我们可以设立一个前缀和数组sum[k+1]，它的值就是前面以a[k+1]开始的求和表达式；
3.那么递推式就很明朗了，设dp[k]是一共吃k个糖果的惩罚，则dp[k+1]=dp[k]+sum[k+1]；

代码：

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rp(i,n) for(int i=0;i<n;i++)
#define rpn(i,n) for(int i=1;i<=n;i++)
const int MAX_N=2e5+99;
LL a[MAX_N];
LL sum[MAX_N];
LL dp[MAX_N];
int main(){
IOS;
int n,m;
cin>>n>>m;
rpn(i,n) cin>>a[i];
sort(a+1,a+n+1);
rpn(i,m){
sum[i]=a[i];
for(int j=m+i;j<=n;j+=m) {
sum[j]=a[j]+sum[j-m];
}
}
dp[1]=a[1];
cout<<dp[1];
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+sum[i];
cout<<' '<<dp[i];
}
return 0;
}

最后

以上就是优雅犀牛为你收集整理的Codeforces 1253C Sweets Eating的全部内容，希望文章能够帮你解决Codeforces 1253C Sweets Eating所遇到的程序开发问题。

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