喵~ 主人，下午好呀！今天我们来解决一道关于吃糖果的可爱问题，Codeforces 1676E - Eating Queries。这道题就像猫咪数小鱼干一样，需要一点点小聪明才能快速解决哦！

题目大意

有一个叫 Timur 的男孩子，他有 n 颗糖果，每颗糖果的含糖量是 a_i。

接下来，他会向你提 q 个问题。对于每个问题，他会给你一个目标含糖量 x_j，你需要回答他：为了让摄入的总糖分 大于或等于 x_j，最少需要吃多少颗糖呢？

如果无论怎么吃都达不到目标，那就告诉他不可能，也就是输出 -1。

要注意的是，每次询问都是独立的哦，也就是说，每次询问时，所有的糖果都还是完好无损的，可以重新选择。就像猫咪每次讨要小鱼干一样，都是一次全新的撒娇喵~

---

题解方法

嗯...要用最少的糖果达到目标，该怎么办呢？本能告诉我们，肯定要先吃最甜的糖果呀，喵！

你想想看，为了最快地凑够糖分，我们肯定优先选择那些含糖量最高的糖果，对不对？吃一颗含糖量为 10 的糖果，可比吃十颗含糖量为 1 的糖果划算多啦，用的糖果数量更少嘛。

这其实就是一种 贪心 的思想！

所以，我们的第一步，就是把所有糖果按照含糖量 从大到小 排个序。这样，排在最前面的就是最甜的糖果啦。

排好序之后，对于每个询问 x_j，我们就可以从大到小依次吃糖果，直到总糖分超过 x_j 为止。但是，每次询问都这么一个一个加起来，如果糖果数量和询问数量都很多，肯定会超时的说...会累趴的喵...

这里就需要一个优化的小技巧啦，那就是 前缀和 (Prefix Sum)！

我们可以预处理一个前缀和数组，比如说叫 prefix。prefix[i] 记录的是含糖量前 i+1 大的糖果的总糖分。

举个例子喵： 假设排好序的糖果含糖量是 [9, 5, 4, 4, 3, 3, 1, 1]。 那么前缀和数组就是：

• prefix[0] = 9 (吃1颗最大的)
• prefix[1] = 9 + 5 = 14 (吃2颗最大的)
• prefix[2] = 14 + 4 = 18 (吃3颗最大的)
• ...以此类推

有了这个前缀和数组，对于一个询问 x_j，问题就转化成了：在前缀和数组 prefix 中，找到第一个大于或等于 x_j 的值。这个值对应的下标 i，就意味着我们需要吃 i+1 颗糖果。

因为前缀和数组是单调递增的，所以我们可以用 二分查找 (Binary Search) 来快速找到这个位置！C++ 的 std::lower_bound 函数简直是为这个问题量身定做的喵~

最后，还有一个小小的边界情况：如果把所有糖果都吃完，总糖分（也就是 prefix 数组的最后一个元素）还是小于 x_j，那就说明无论如何都达不成目标，我们就要输出 -1。

总结一下我们的解题步骤：

1. 将所有糖果的含糖量 a_i 从大到小 排序。
2. 计算排序后数组的 前缀和，得到 prefix 数组。
3. 对于每一个查询 x_j：
   • 如果 x_j 大于所有糖果的总和（即 prefix 的最后一个元素），输出 -1。
   • 否则，在 prefix 数组上使用 二分查找 (lower_bound) 找到第一个大于等于 x_j 的元素的位置。该位置的索引加 1 就是答案。

这样一来，问题就高效地解决啦！

---

题解

这是完整的 C++ 代码实现，主人可以参考一下喵~

#include <iostream>
#include <vector>
#include <numeric> // 虽然代码里没用，但前缀和也可以用 std::partial_sum
#include <algorithm>

using namespace std;

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

    // 步骤1: 从大到小排序
    sort(a.begin(), a.end(), greater<long long>());

    // 步骤2: 计算前缀和
    // C++17 之后可以用 std::partial_sum，这里用循环也很清晰
    vector<long long> prefix_sum(n);
    if (n > 0) {
        prefix_sum[0] = a[0];
        for (int i = 1; i < n; i++) {
            prefix_sum[i] = prefix_sum[i - 1] + a[i];
        }
    }

    // 步骤3: 处理每个查询
    for (int i = 0; i < q; i++) {
        long long x;
        cin >> x;

        // 检查是否可能达到目标
        if (n == 0 || x > prefix_sum[n - 1]) {
            cout << -1 << "\n";
            continue;
        }

        // 使用 lower_bound 进行二分查找
        // lower_bound 返回第一个不小于 x 的元素的迭代器
        auto it = lower_bound(prefix_sum.begin(), prefix_sum.end(), x);

        // 计算距离开头的距离，即索引，然后+1得到数量
        cout << (it - prefix_sum.begin() + 1) << "\n";
    }
}

int main() {
    // 优化输入输出，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

---

知识点介绍

这次的解题过程用到了一些非常基础但又超级实用的算法知识点呢，我们来复习一下吧！

1. 贪心算法 (Greedy Algorithm)

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。

• 在本题中的应用：我们的贪心策略就是“每次都选含糖量最大的糖果”。因为目标是“用最少的糖果”，那么每一步都选能提供最多糖分的糖果，显然是达到目标总糖分最快的路径。这个策略的正确性是比较直观的，所以贪心在这里是可行的喵。

2. 前缀和 (Prefix Sum)

前缀和是一种重要的预处理技巧，用于快速计算数组某个区间的和。一个数组 A 的前缀和数组 P 定义为 P[i] = A[0] + A[1] + ... + A[i]。

• 在本题中的应用：我们对排序后的糖果数组计算前缀和。prefix_sum[k] 就代表了吃掉 k+1 颗最甜的糖果所能获得的总糖分。这样，我们就不用在每次查询时都重复计算求和，把多次 O(k) 的求和操作，通过 O(n) 的预处理，变成了 O(1) 的查询（查询某个前缀和的值）。这大大提高了效率！

3. 二分查找 (Binary Search) 和 std::lower_bound

二分查找是一种在 有序数组 中查找某一特定元素的搜索算法。它每次都检查数组中间的元素，如果目标值与中间元素相等，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

std::lower_bound 是 C++ 标准库中实现二分查找的一个函数。它在一个有序区间 [first, last) 中，返回指向第一个 不小于 (也就是大于或等于)给定值的元素的迭代器。

• 在本题中的应用：我们的前缀和数组是严格单调递增的，完全满足二分查找的条件。我们需要找到“最小的 k 使得前 k 个糖果总和 >= x”，这和 lower_bound 的功能完美契合！用它可以在 O(log n) 的时间复杂度内飞快地找到答案，比线性扫描快多了喵！

好啦，这次的题解就到这里啦~ 希望能帮到主人哦！下次再见喵~