Problem F. For the treasury!

问题描述

Askeladd 取得了按顺序排列的 n 件宝物，次日需分配给自己前 k 件，其余给同伙。但他可以在夜里通过任意次「相邻宝物交换」重新排列宝物，每次交换成本为 c。求考虑交换成本后，他能拿到的最大 “净值”（宝物总价值 − 交换总成本）。

输入

  • 第一行：整数 n, k 和交换成本 c。
  • 第二行：n 个整数 a₁, a₂, …, aₙ，表示当前宝物的价值。

约束

  • 0 ≤ k ≤ n ≤ 3×10⁵
  • 0 ≤ c ≤ 10⁹
  • 1 ≤ aᵢ ≤ 10⁹

输出

获得的最大净值。

思路

1. 等价转换

若某宝物原在位置 i（1-based），需调到前 k 个位置中的第 j 个位置（1-based），则交换次数为 i - j（向左移动跨过的次数），总成本为 c×(i - j)。 该宝物的 “贡献值”（净值）为： (a_i - c×(i - j) = (a_i - c×i) + c×j)

2. 降维：加权排序

对前 k 件宝物的总贡献值求和： ($\sum_{选中的k件} \left[(a_i - c×i) + c×j\right]$ = $\sum_{选中的k件}(a_i - c×i) + c×\sum_{j=1}^k j$)

其中，$\sum_{j=1}^k j = \frac{k(k+1)}{2}$ 是常数（与具体选哪 k 件无关）。因此，问题简化为：从所有宝物中选 k 件，使 $\sum (a_i - c×i)$ 最大。

实现细节

  1. 构造数组：定义 b_i = a_i - c×i（i 为 1-based 位置）。
  2. 选最大 k 项：从 b 中选出最大的 k 个元素，求和得 sumB。
  3. 计算常数项：$c×\sum_{j=1}^k j = c×\frac{k(k+1)}{2}$。
  4. 最终答案：sumB + 常数项。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    ll c;
    cin >> n >> k >> c;

    // 构造数组 b_i = a_i - c * i（i为1-based位置）
    vector<ll> b(n);
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        b[i] = a - c * (i + 1LL);  // i是0-based，位置为i+1
    }

    // 特殊情况：k=0时，不拿任何宝物，净值为0
    if (k == 0) {
        cout << 0 << "\n";
        return 0;
    }

    // 从b中选最大的k个元素：用nth_element高效划分
    nth_element(b.begin(), b.begin() + k, b.end(), greater<ll>());

    // 累加前k个最大元素的和
    ll sumB = 0;
    for (int i = 0; i < k; i++) {
        sumB += b[i];
    }

    // 计算常数项：c * (1+2+...+k)
    ll sumPos = (ll)k * (k + 1) / 2;

    // 最终答案
    ll ans = sumB + c * sumPos;
    cout << ans << "\n";

    return 0;
}

复杂度分析

O(n)