第3题-专栏改挂后的最大综合评分

小红书9月13日机考题目与解析

某技术社区举办「全能作者季」。你在 $n$ 个专栏方向上各有若干成稿：第 $i$ 个方向现有 $a_i$ 篇。

你可以把一篇成稿从方向 $i$ 改挂到方向 $j$（须保证该方向改挂后篇数非负）。每改挂一篇计一次操作，最多操作 $k$ 次。

改挂结束后，设 $x$ 为成稿数不少于 $b$ 篇的方向个数，$y = \min(a_1, a_2, \ldots, a_n)$，综合评分定义为

$$x \cdot c_1 + \min(y, b) \cdot c_2$$

保证 $c_1 \ge c_2$。请最大化综合评分。

输入描述

第一行五个整数 $n$、$k$、$b$、$c_1$、$c_2$。
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

输出描述

输出一个整数，表示可达到的综合评分最大值。

约束条件：$1 \le n \le 10^5$；$0 \le k, a_i \le 10^9$；$1 \le b, c_1, c_2 \le 10^9$；$c_1 \ge c_2$。

样例 1

输入：

5 3 4 4 1
1 2 5 0 3

输出：

9

说明：从第 3 个方向改挂 1 篇到第 5 个方向，再从第 2 个方向改挂 1 篇到第 4 个方向，各方向成稿数为 $[1,1,4,1,4]$。此时 $x=2$，$y=1$，$\min(y,b)=1$，评分为 $2 \times 4 + 1 \times 1 = 9$。

代码

n, k, b, c1, c2 = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

# 前缀和
pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + a[i]

total = pre[n]

# cost[i] = 把前 i 个元素都提升到 a[i-1] 所需操作数
cost = [0] * (n + 1)
for i in range(1, n + 1):
    cost[i] = a[i - 1] * i - pre[i]

ans = 0
cost_b = 0          # 让最大的 x 个方向达到 b 的最小花费
cnt = n             # 单调指针，维护最大的满足 cost[cnt] <= rest 的 cnt

for x in range(n + 1):
    # 至少需要 x * b 篇，总篇数不够则不可能
    if total < x * b:
        break
    # cost_b 单调不减，一旦超过 k，后续 x 更不可能
    if cost_b > k:
        break

    m = n - x
    if m == 0:
        # 所有方向都 >= b
        ans = max(ans, x * c1 + b * c2)
    else:
        rest = k - cost_b

        # 剩余的是最小的 m 个方向，cnt 只减不增
        if cnt > m:
            cnt = m
        while cnt > 1 and cost[cnt] > rest:
            cnt -= 1

        # 用剩余预算尽量抬高这 m 个方向的最小值
        y1 = a[cnt - 1] + (rest - cost[cnt]) // cnt
        # 总篇数限制下的最大值
        y2 = (total - x * b) // m
        y = min(b, y1, y2)

        ans = max(ans, x * c1 + y * c2)

    # 为下一个 x 累加花费：把剩余中最大的那个提升到 b
    if m > 0:
        cost_b += max(0, b - a[m - 1])

print(ans)

逐段解析

一、问题回顾

有 n 个方向，每个方向有 a[i] 篇成稿。最多进行 k 次改挂操作：每次从某个方向拿 1 篇放到另一个方向（保证来源非负）。改挂后：

• x：成稿数 ≥ b 的方向个数；
• y = min(a[1..n])：所有方向中的最小成稿数；
• 综合评分 = x * c1 + min(y, b) * c2。

已知 c1 >= c2，要求最大化评分。

二、整体思路

1. 排序：将 a 从小到大排序。这样方便贪心选择最大的若干个方向去满足 b，以及处理剩余的最小若干个方向。
2. 枚举 x：最终有多少个方向的成稿数 ≥ b。x 从 0 到 n。
3. 贪心满足 b：为了让操作次数最少，一定选择原本最大的 x 个方向去补到 b。记录这个最小花费 cost_b。
4. 处理剩余方向：剩下 m = n - x 个方向（它们是最小的 m 个）。用剩余操作数 rest = k - cost_b 尽可能提高这 m 个方向的最小值 y。
5. 计算评分：x * c1 + min(y, b) * c2，更新最大值。

三、代码逐段解释

输入与预处理：

data = list(map(int, sys.stdin.buffer.read().split()))
n, k, b, c1, c2 = data[:5]
a = data[5:5 + n]
a.sort()
pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + a[i]
total = pre[n]

• 快速读入所有数据。
• a 排序后，pre[i] 表示前 i 个元素的和。
• total 是所有成稿的总数。改挂操作不改变总篇数。

cost = [0] * (n + 1)
for i in range(1, n + 1):
    cost[i] = a[i - 1] * i - pre[i]

• cost[i]：把最小的 i 个元素都提升到 a[i-1] 所需的操作数。
  • 例如 i=3，最小的三个是 a[0], a[1], a[2]，都拉到 a[2]，需要增加 (a[2]-a[0]) + (a[2]-a[1]) + 0 = 3*a[2] - (a[0]+a[1]+a[2]) = a[2]*3 - pre[3]。
• 这个数组用于后续快速计算「拉平」最小若干个元素的花费。

主循环：枚举 x：

ans = 0
cost_b = 0          # 让最大的 x 个方向达到 b 的最小花费
cnt = n             # 单调指针，维护最大的满足 cost[cnt] <= rest 的 cnt
for x in range(n + 1):
    if total < x * b:
        break
    if cost_b > k:
        break
    m = n - x
    if m == 0:
        ans = max(ans, x * c1 + b * c2)
    else:
        rest = k - cost_b
        if cnt > m:
            cnt = m
        while cnt > 1 and cost[cnt] > rest:
            cnt -= 1
        y1 = a[cnt - 1] + (rest - cost[cnt]) // cnt
        y2 = (total - x * b) // m
        y = min(b, y1, y2)
        ans = max(ans, x * c1 + y * c2)
    if m > 0:
        cost_b += max(0, b - a[m - 1])

循环条件：

• total < x * b：总篇数不足以让 x 个方向都达到 b，后续更大的 x 更不可能，直接退出。
• cost_b > k：让最大的 x 个方向达到 b 的花费已经超过 k，后续 x 更大花费更多，退出。

处理 m == 0：

• 所有方向都达到了 b，此时 y >= b，所以 min(y, b) = b。
• 评分 = x * c1 + b * c2。

处理剩余 m 个方向：

• rest = k - cost_b：剩余可用操作数。
• m = n - x：剩余方向个数，它们是最小的 m 个（因为最大的 x 个已经被补到 b）。
• 单调指针 cnt：
  • 我们要用 rest 次操作提高这 m 个方向的最小值。
  • 策略：把最小的 cnt 个方向「拉平」到 a[cnt-1]。所需花费为 cost[cnt]。
  • 随着 x 增大，m 减小，rest 减小，所以满足 cost[cnt] <= rest 的最大 cnt 只会减小。因此用全局指针 cnt 从大到小移动即可，无需二分。
  • if cnt > m: cnt = m 保证 cnt 不超过剩余方向数。
  • while cnt > 1 and cost[cnt] > rest: cnt -= 1 找到最大的可行 cnt。
• 计算 y1：
  • 拉平前 cnt 个到 a[cnt-1] 后，还剩 rest - cost[cnt] 次操作。
  • 平均分给这 cnt 个方向，每个还能增加 (rest - cost[cnt]) // cnt 篇。
  • 所以这 cnt 个方向的最小值可达 y1 = a[cnt-1] + (rest - cost[cnt]) // cnt。
• 计算 y2：
  • 总篇数限制：已经保证 x 个方向各有至少 b 篇，占用了 x * b 篇。
  • 剩余 m 个方向总共最多有 total - x * b 篇，平均每个方向最多 y2 = (total - x * b) // m 篇。
• 最终 y：不能超过 b（评分只取 min(y, b)）、不能超过 y1（操作数限制）、不能超过 y2（总篇数限制），所以 y = min(b, y1, y2)。
• 更新答案：ans = max(ans, x * c1 + y * c2)。

为下一个 x 更新 cost_b：

• 当前 m = n - x，剩余方向中最大的是 a[m-1]（数组已排序，最大的 x 个被移除，剩下索引 0 到 m-1）。
• 下一个 x 会多让一个方向达到 b，这个方向就是当前剩余中最大的 a[m-1]。
• 将它提升到 b 需要 max(0, b - a[m-1]) 次操作，累加到 cost_b。

四、为什么正确？

1. 贪心选择最大的 x 个去满足 b：因为这样花费最少，剩下的操作数最多，有利于提高最小值。
2. 拉平策略最大化最小值：在剩余操作数下，要让一组数的最小值最大，最优做法就是先把最小的若干个「拉平」到某个值，再均分剩余操作数。
3. 单调指针代替二分：随着 x 增大，剩余方向数 m 和剩余操作数 rest 都单调不增，所以满足 cost[cnt] <= rest 的最大 cnt 也单调不增。指针只需从 n 递减，总移动次数 O(n)。
4. 总篇数与 b 的限制：通过 y2 和 min(b, ...) 正确处理。

五、复杂度

• 排序：O(n log n)
• 主循环：O(n)
• 单调指针总移动：O(n)
• 总时间复杂度：O(n log n)，空间复杂度 O(n)