一个贪心+二分查找的编程问题

Question

• 问题描述： 莲养了一头猪，想把它卖到市场上。市场上的猪需要有质量保证，至少m公斤。他有n袋饲料要喂猪，每袋的重量是一公斤。如果猪每天吃多于一袋，它们的吸收就会开始减少，第二袋-1，第三袋-2，以此类推。 Lian养的猪至少要多少天才能达标？

• 输入： 第一行有两个整数n，m。 第二行有n个整数代表dr.

• 输出： 打印 Lian 至少需要多少天才能让他的猪达到标准。如果 Lian 无法让他的猪达到标准，则打印 -1。

输入 1： 5 5 1 1 1 1 1

输出 1： 5

输入 2： 10 40 5 5 5 5 5 5 5 5 5 5

输出 2： 4

输入 3： 10 56 1 2 3 4 5 6 7 8 9 10

输出 3： -1

• 约束： 1 <= n <= 200000, m is in int range, 1 <= a <= 10000

这是一个关于贪心算法和二分查找算法的问题，我只能想到贪心部分：先喂大权重的袋子，二分查找部分我不懂

Answer 1

我们可以使用二分查找法找到将猪养到规定重量所需的最少天数。假设答案介于 1 和所有饲料袋的总和之间。

然后，我们检查是否可以在该天数内将猪饲养到所需的重量。

• 如果可能的话，找一个更小的天数 检查间隔的左半部分。
• 如果不可能，找到更大的天数 检查间隔的右半部分。

继续这个过程，直到我们得到所需的最少天数或确定无法将猪饲养到所需的重量。

这是相同的代码。

bool check(vector<int>v, int maxDays , const int req) {
    const int n=v.size();
    int sum=0;
    for(int i=0;i<min(n,maxDays);i++){
        sum+=v[i];
        if(sum>=req){
            return true;
        }
    }
    int days=1;
    int cnt=1;
    for(int i=maxDays;i<v.size();i++){
        if(days>maxDays){
            days=1;
            cnt++;
        }
        if(v[i]-cnt<=0)break;
        sum+=v[i]-cnt;
        if(sum>=req)break;
        days++;
    }
    return sum>=req;
}

void solution() {
    int n, m;
    cin >> n >> m;
    vector<int>v(n);
    sort(v.begin(), v.end(), [&](const int &a, const int&b) {
        return a >= b;
    });
    int ans = -1;
    int start = 0, end = 2*n;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (check(v, mid, m)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    cout << ans << "\n";
}