题目重述与分析

妮妮学姐有一个长度为 n的数组 a，需要执行 k次操作，每次操作有两种选择：

1. 操作A：取走当前数组中的最大元素（消耗1次操作，取走1个元素）
2. 操作B：取走当前数组中的最小和次小元素（消耗1次操作，取走2个元素）

目标是在 k次操作后，取走的元素总和最小。

关键约束：2k<n，这意味着无论如何选择操作，都不会取完所有元素。

核心洞察

1. 操作类型的数学关系

设：

• b：执行操作B的次数
• k−b：执行操作A的次数

那么总共取走的元素数量为：

取走元素数=(k−b)×1+b×2=k+b

2. 排序的必然性

由于操作只涉及数组的极值（最大、最小、次小），我们可以先对数组排序，将小元素放在左边，大元素放在右边。

排序后，操作B总是从数组左端取元素，操作A总是从数组右端取元素。

3. 不重叠性保证

约束条件 2k<n确保了左右取走的元素不会重叠：

左端取走=2b右端取走=k−b

总取走=2b+(k−b)=k+b≤2k<n

因此左右两端的操作是独立的。

算法设计

1. 枚举策略

我们无法直接确定最优的 b值，但可以枚举所有可能的 b值（从0到 k），计算每种情况下的总和，取最小值。

对于每个 b：

• 左端和 = 最小的 2b个元素的和
• 右端和 = 最大的 k−b个元素的和
• 总和 = 左端和 + 右端和

2. 高效计算

通过前缀和预处理，我们可以在 O(1)时间内计算任意区间的和：

• 前缀和 pref[i]表示前 i个元素的和
• 最小的 2b个元素的和 = pref[2b]
• 最大的 k−b个元素的和 = 总和 – 前 n−(k−b)个元素的和

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 排序：小元素在左，大元素在右
    sort(a.begin(), a.end());
    
    // 计算前缀和
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + a[i];
    }
    
    long long total_sum = pref[n];
    long long ans = 1e18;  // 初始化为一个很大的数
    
    // 枚举操作B的次数b
    for (int b = 0; b <= k; b++) {
        // 左端：最小的2b个元素（操作B取走的）
        long long left_sum = pref[2 * b];
        
        // 右端：最大的k-b个元素（操作A取走的）
        int right_count = k - b;
        long long right_sum = total_sum - pref[n - right_count];
        
        // 更新最小值
        ans = min(ans, left_sum + right_sum);
    }
    
    cout << ans << endl;
    
    return 0;
}

代码详解

1. 输入与初始化

int n, k;
cin >> n >> k;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}

读取数组长度、操作次数和数组元素。使用 long long防止大数溢出。

2. 排序与前缀和

sort(a.begin(), a.end());
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; i++) {
    pref[i + 1] = pref[i] + a[i];
}
long long total_sum = pref[n];

排序后，a[0]是最小值，a[n-1]是最大值。前缀和数组 pref[i]表示前 i个元素的和。

3. 枚举核心逻辑

for (int b = 0; b <= k; b++) {
    long long left_sum = pref[2 * b];
    int right_count = k - b;
    long long right_sum = total_sum - pref[n - right_count];
    ans = min(ans, left_sum + right_sum);
}

对于每个可能的 b值：

• left_sum：最小的 2b个元素的和（直接通过前缀和获取）
• right_sum：最大的 k−b个元素的和（总和减去前 n−(k−b)个元素的和）

4. 极端情况验证

• 当 b=0：全操作A，取最大的 k个元素
• 当 b=k：全操作B，取最小的 2k个元素
• 当 b取中间值：混合策略，平衡大小元素的取舍

时间复杂度分析

• 排序：O(nlogn)
• 前缀和计算：O(n)
• 枚举 b：O(k)
• 总复杂度：O(nlogn+k)，满足题目要求

示例验证

输入：

5 2
1 2 3 4 5

排序后：[1, 2, 3, 4, 5]

枚举 b：

• b=0：左和=0，右和=4+5=9，总和=9
• b=1：左和=1+2=3，右和=5，总和=8
• b=2：左和=1+2+3+4=10，右和=0，总和=10

最优解：b=1，总和=8

总结

这道题看似复杂，实则是典型的双端贪心+枚举问题。通过排序和前缀和技巧，将问题转化为简单的区间和计算。约束条件 2k<n确保了左右操作的独立性，使得枚举策略可行且高效。