Sweets Eating(前缀和的妙用)

74 阅读 0 评论 49 点赞

我是靠谱客的博主纯真魔镜，最近开发中收集的这篇文章主要介绍Sweets Eating(前缀和的妙用)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem - 1253C - Codeforces

鹤木给轻音乐俱乐部带来了n个美味的糖果。它们的编号从1到n，其中第i种糖果的糖浓度用整数ai来描述。

Yui喜欢甜食，但出于健康原因，她每天最多可以吃m个甜食。

日子以1为单位（编号为1,2,3,...）。在第d天吃甜食i将导致(d⋅ai)的糖分惩罚，因为甜食的糖分会随着时间的推移而增加。一个甜食最多只能吃一次。

总的糖分惩罚将是所吃的每种甜食的单独惩罚之和。

假设Yui正好选择了k种甜食，并按照她想要的顺序吃了它们。她能得到的最小总糖分是多少？

由于Yui是一个不确定的女孩，她希望你能回答这个问题，因为k的每个值都在1到n之间。

输入
第一行包含两个整数n和m（1≤m≤n≤200 000）。

第二行包含n个整数a1,a2,...,an（1≤ai≤200 000）。

输出
你必须在一行中输出n个整数x1,x2,...,xn，用空格隔开，其中xk是Yui如果正好吃了k个甜食所能得到的最小的总糖分。

例子
inputCopy
9 2
6 19 3 4 4 2 6 7 8
outputCopy
2 5 11 18 30 43 62 83 121
输入复制
1 1
7
输出拷贝
7
注意
让我们分析一下第一个例子中k=5的答案。下面是吃5种甜食的可能方法之一，这些方法可以使总的糖分惩罚最小化。

第一天：甜食1和4
第二天：甜食5和3
第三天：甜食6
总惩罚是1⋅a1+1⋅a4+2⋅a5+2⋅a3+3⋅a6=6+4+8+6+6=30。我们可以证明这是Yui如果吃了5个甜食所能达到的最小总糖分惩罚，因此x5=30。

s[i] = a[i] + s[i - m];核心代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int a[200059];
ll s[200050];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1;i <= n ;i ++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
for(int i = 1;i <= n ;i++)
{
if(i < m)
{
s[i] = a[i];
}
else
{
s[i] = a[i] + s[i - m];
}
}
ll ans = 0;
for(int i = 1;i <= n;i ++)
{
ans += s[i];
printf("%lld ",ans);
}
}