Submission #72534531

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 3e5 + 10;

ull a[N], pre_sum[N]; // 前缀和数组，pre_sum[i]是前i个杯子的体积和（降序）

int main() {
    int n, k;
    ull x;
    scanf("%d%d%llu", &n, &k, &x);
    for (int i = 1; i <= n; ++i) {
        scanf("%llu", &a[i]); // 用ull存储，避免输入溢出
    }
    
    // 降序排序
    sort(a + 1, a + n + 1, greater<ull>());
    
    // 预处理前缀和
    pre_sum[0] = 0;
    for (int i = 1; i <= n; ++i) {
        pre_sum[i] = pre_sum[i - 1] + a[i];
    }
    
    // 二分查找最小的m
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        // 计算t：选中m个杯子时，最坏情况下能拿到的清酒杯子数
        int t = max(0, m + k - n);
        if (t == 0) {
            // 最坏情况拿不到清酒，和为0，不满足
            l = m + 1;
            continue;
        }
        // 前m个中最后t个的和 = pre_sum[m] - pre_sum[m - t]
        ull sum = pre_sum[m] - pre_sum[m - t];
        if (sum >= x) {
            ans = m;
            r = m - 1; // 找更小的m
        } else {
            l = m + 1;
        }
    }
    
    printf("%d\n", ans);
    return 0;
}

Submission Info

Judge Result