第2题-行为权重2

题目

在小红书的推荐引擎中，为了评估用户行为序列的「权重」对内容分发的影响，平台将用户的一系列操作映射为一个长度为 $n$ 的数值数组 $(a_1, a_2, \ldots, a_n)$。系统需要对前 $m$ 步行为进行聚合评估，但允许丢弃（删除）多达 $n - m$ 步「噪声」操作，每删除一步需支付权值 $k$ 的代价。

具体地，对于每个 $m$（$1 \le m \le n$），在原数组上最多执行 $n - m$ 次删除操作（删除任意位置的 $a_i$，结果不影响下次计算），然后计算：删除次数 $\times k + \sum_{i=1}^{m} a_i$，其中 $\sum_{i=1}^{m} a_i$ 是对删完后新数组的前 $m$ 项求和。

你需要对每一个 $m$ 输出对应的最小代价。

注意：对于每个 $m$ 的计算都是独立的，每次都从完整的初始数组 $a$ 开始。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T$ 代表数据组数。每组测试数据： 第一行输入两个整数 $n, k$，分别代表行为序列长度和删除代价。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示原始行为权重。

输出描述

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

（回忆版无样例，可直接用代码自测）

思路

枚举前缀 + 排序 + 前缀和：保留的 $m$ 个数必然来自原数组的某个前缀 $a[0..p-1]$（$p \ge m$，$p$ 是「用到的最远位置」），且应取其中最小的 $m$ 个（求和与顺序无关）。把 $a[0..p-1]$ 排序后做前缀和，$pre[m]$ 即最小 $m$ 个数之和，代价为 $(p - m) \cdot k + pre[m]$；对每个 $m$ 取所有 $p$ 的最小值。复杂度 $O(n^2 \log n)$。

代码

import sys

def main():
    it = iter(sys.stdin.read().strip().split())
    t = int(next(it))
    inf = 1 << 60
    for _ in range(t):
        n, k = int(next(it)), int(next(it))
        a = [int(next(it)) for _ in range(n)]

        ans = [inf] * (n + 1)
        for p in range(1, n + 1):  # 用到的最远位置
            b = a[:p]
            b.sort()
            pre = [0]
            for x in b:
                pre.append(pre[-1] + x)
            for m in range(1, p + 1):
                cost = (p - m) * k + pre[m]
                if cost < ans[m]:
                    ans[m] = cost
        print(" ".join(str(i) for i in ans[1:]))

if __name__ == "__main__":
    main()

来源：25秋招笔试真题-小红书0907（知乎专栏）（回忆版）