只需要在原数组前缀中删除。设最终新数组的第 $m$ 个元素在原数组中的位置为 $p$ （ $m$ ≤ $p$ ≤ $n$ ）。要让它成为新数组的第 $m$ 个，需要把前 $p$ 个元素中恰好删除 $p−m$ 个，后面的元素无需删除（删了也只会增加代价）。
为使前 $m$ 个保留元素的和值最小，应从前 $p$ 个元素里挑出值最小的 $m$ 个。

P3625.第2题-行为权重2

1000ms

Difficulty: 3

所属公司 : 小红书

算法与标签>贪心算法

题目内容

在小红书的推荐引擎中，为了评估用户行为序列的“权重”对内容分发的影响，平台将用户的一系列操作映射为一个长度为 $n$ 的数值数组 $(a_1,a_2,…,a_n)$ 。

系统需要对前 $m$ 步行为进行聚合评估，但允许丢弃(删除)多达 $n-m$ 步“噪声”操作，每删除一步需支付权值 $k$ 的代价。

具体地，对于每个 $m(1≤m≤n)$ ，在原数组上最多执行 $n-m$ 次删除操作(删除任意位置的 $a_i$ ，结果不影响下次计算)，然后计算:

$删除次数*k+\sum^m_{i=1}a_i$

其中 $\sum^m_{i=1}a_i$ 是对删完后新数组的前 $m$ 项求和。

你需要对每一个 $m(1≤m≤n)$ 输出对应的最小代价。请注意，对于每个 $m$ 的计算都是独立的，每次都从完整的初始数组 $a$ 开始。

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≤T≤50)$ 代表数据组数，每组测试数据描述如下:

第一行输入两个整数 $n,k(1≤n≤10^3,1≤k≤2*10^5)$ ,分别代表行为序列长度和删除代价。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≤a≤2*10^5)$ 表示原始行为权重。除此之外，保证单个测试文件的 $n$ 之和不超过 $10^3$ 。

对于每个测试用例，新起一行输出 $n$ 个整数，第 $m$ 个数表示当保留前 $m$ 步行为时的最小代价，按 $m$ 从 $1$ 到 $n$ 顺序用空格分隔。

输入

1
3 1
4 2 3

输出

3 6 9

说明

在这个样例中:

$m = 1$ 时，最优策略为删除原数组的 $a_1=4$ ,得到新数组 { $2,3$ } ;最终值为 $1×1+(2)=5$

$m=2$ 不删除，最终值为 $0×1+(4+2)=6$ 。

$m=3$ 不删除，最终值为 $0×1+(4+2+3)= 9$ 。

输入

预期输出（选填）