C++ 实现巧克力装包问题：二分答案 + 前缀和

问题描述：

有 n 个巧克力，每个巧克力都是厚度一样的正方形巧克力板，边长分别为 a1, a2... an，认为第 i 个巧克力的重量为 ai²。

第一行输入两个整数 n 和 m，表示巧克力数量和小美询问数量。

第二行 n 个整数 a1, a2.. an 表示 n 块正方形巧克力板的边长，注意不能将巧克力板进行拆分。

第三行 m 个整数 q1, q2... qn 第 i 个整数 qi 表示询问：如果小美选择一个能装 qi 重量的钱包，最多能装多少巧克力板？

1 <= n, m <= 50000，1 <= ai <= 10 四次方, 1 <= qi <= 10 十八次方

输出一行 m 个整数，表示每次询问的答案。

思路：

二分答案 + 前缀和

首先我们可以发现，如果小美选择的钱包能装下 x 块巧克力板，那么一定能装下 1~x 块巧克力板，因此我们可以二分答案 x，然后判断能否将前 x 块巧克力板放入小美的钱包中。

具体实现中，我们可以先将巧克力板按重量从小到大排序，然后用前缀和维护前 i 块巧克力板的重量和，这样就可以 O(1) 得到前 i 块巧克力板的重量。

在判断能否放入小美的钱包时，我们可以用双指针维护一个区间，使得这个区间内的巧克力板的重量和不超过小美的钱包能装的重量。具体的，我们可以先将左指针和右指针都指向 1，然后不断地将右指针向右移动，直到区间内的巧克力板的重量和超过了小美的钱包能装的重量，此时我们再将左指针向右移动，直到区间内的巧克力板的重量和不超过小美的钱包能装的重量，然后记录区间长度，并将右指针向右移动一个位置，继续寻找下一个区间。

最后，我们将所有能装下的巧克力板数目的最大值作为答案即可。

时间复杂度：

排序的复杂度为 O(nlogn)，二分答案的复杂度为 O(mlogn)，双指针的复杂度为 O(n)，因此总的时间复杂度为 O(nlogn+mlogn+n)=O((m+n)logn)。

代码实现：

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] *= a[i]; // 计算巧克力重量
    }
    vector<long long> q(m);
    for (int i = 0; i < m; ++i) {
        cin >> q[i];
    }
    sort(a.begin(), a.end()); // 按重量排序
    vector<long long> sum(n + 1, 0); // 前缀和
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + a[i - 1];
    }
    for (int i = 0; i < m; ++i) {
        long long left = 1, right = n, ans = 0;
        while (left <= right) {
            long long mid = (left + right) / 2;
            if (sum[mid] <= q[i]) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        cout << ans << ' ';
    }
    return 0;
}