神奇的口袋 注意数据范围

Question

蜗蜗有一个神奇的口袋，口袋可以装下体积总和为 m 的宝石。

一共有 n+1 种不同的宝石。第 i (1≤i≤n) 种宝石一共有 ai 颗，每一颗的体积都是 bi。第 n+1 种宝石有无限多颗，每一颗的体积都是 1。

现在蜗蜗想用数量最少的宝石装满口袋，请求出蜗蜗最少要使用多少颗宝石。
输入格式

第一行一个正整数 test 表示数据组数。

对于每组数据，第一行两个整数 n,m。接下来 n 行，每行两个整数 ai,bi 分别表示一种宝石的数量和体积。
输出格式

对于每组数据，输出一行一个整数，表示蜗蜗最少要使用多少颗宝石。
样例输入

2
2 7
1 2
1 4
2 6
1 2
1 4

样例输出

3
2

数据规模

对于 30% 的数据，保证所有的 ai=1。

对于 100% 的数据，保证 1≤test≤10^5,1≤n≤31,0≤m<2^31,1≤ai<2^31,2≤bi<2^31，bi 已经从小到大排好序了并且两两不同。

C++
这题目有点难，能否帮帮我

Answer 1

先读入数据，用一个数组 a 存储宝石数量，用一个数组 b 存储宝石体积。然后，用一个变量 sum 记录当前已经装入口袋的宝石体积总和，用一个变量 cnt 记录已经装入的宝石数量。接下来，遍历每种宝石，如果当前宝石体积加上 sum 小于等于口袋容量 m，则将该宝石体积加入 sum，并将 cnt 加 1；如果当前宝石体积加上 sum 大于 m，则需要判断是否能够舍弃当前宝石而使得 sum 更接近 m。具体来说，如果后面宝石的体积与当前宝石体积之差大于 m-sum，则舍弃当前宝石，否则需要判断左右两个区间的大小，并计算出需要舍弃的宝石数量。最后，输出 cnt 的值即可。下面是一个例子：

#include <iostream>
using namespace std;

int main() {
    int test;
    cin >> test;
    while (test--) {
        int n, m;
        cin >> n >> m;
        int a[100005], b[100005];
        for (int i = 1; i <= n; i++) {
            cin >> a[i] >> b[i];
        }
        int sum = 0, cnt = 0;
        bool flag = false;
        for (int i = 1; i <= n; i++) {
            if (!flag && sum + b[i] <= m) {
                sum += b[i];
                cnt++;
            } else if (sum == m) {
                break;
            } else {
                flag = true;
                if (i == n || b[i+1] - b[i] > m - sum) {
                    cnt++;
                    sum += b[i];
                } else {
                    int diff = m - sum;
                    int left = i - 1, right = i + 1;
                    while (left >= 1 && b[left] - b[i] >= diff) left--;
                    while (right <= n && b[right] - b[i] >= diff) right++;
                    if (right - left >= 2) {
                        cnt += right - left - 1;
                    } else {
                        cnt++;
                    }
                    sum += b[i];
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}