贪心+二分查找编程问题咨询：猪达标最小天数的二分逻辑疑问

问题回顾 #

连养的猪需要至少达到m千克才能出售，现有n袋饲料，每袋重量为a_i。猪每天吃饲料的规则是：当天吃第1袋全吸收，第2袋吸收量减1千克，第3袋减2千克，以此类推（即第k袋有效吸收量为max(a_i - (k-1), 0)）。求让猪达标所需的最少天数，若总有效吸收量不足m则输出-1。

核心思路：贪心+二分查找 #

你提到的优先投喂重量更大的饲料是关键贪心策略——大重量饲料在减重幅度小的时段投喂，能最大化总吸收量。而二分查找的作用是快速定位最少需要的天数，避免暴力枚举的低效。

为什么要用二分查找？ #

这个问题天然满足单调性，是二分查找的典型适用场景：

• 若d天能让猪达标，那么所有大于d的天数肯定也能达标（天数越多，可投喂的饲料越多，总吸收量只会更大或不变）
• 若d天无法达标，那么所有小于d的天数也必然不行

利用这个单调性，我们可以在天数的可能范围内快速缩小搜索范围，找到最小的可行天数。

二分查找的具体实现 #

1. 确定二分范围

• 左边界left=1（最少需要1天）
• 右边界right=n（最坏情况每天只喂1袋，需要n天）
• 前置判断：先计算所有饲料不被减重的总重量（即每天喂1袋的总吸收量），如果这个值小于m，直接返回-1。

2. 判断某天数mid是否可行

给定天数mid，我们需要计算用mid天投喂时，能达到的最大总吸收量：

1. 先将饲料按重量从大到小排序（贪心策略的体现）
2. 对排序后的第i袋饲料（从0开始计数）：
   • 它会被分配到第(i // mid) + 1次投喂位（比如mid=4天，第0-3袋是每天的第1次投喂，第4-7袋是每天的第2次投喂，以此类推）
   • 对应的减重量为i // mid（第1次投喂减0，第2次减1，以此类推）
   • 该袋的有效吸收量为max(a_i - (i // mid), 0)
3. 累加所有饲料的有效吸收量，若总和≥m，说明mid天可行。

3. 二分迭代过程

• 若mid天可行：尝试找更小的天数，将右边界right=mid-1，同时记录当前mid为候选答案
• 若mid天不可行：需要更多天数，将左边界left=mid+1
• 当left>right时，记录的候选答案就是最少天数

结合示例理解 #

以输入2为例：

10 40
5 5 5 5 5 5 5 5 5 5

• 尝试mid=4天：
  前4袋（i=0-3）是每天第1次投喂，减0，每袋吸收5；
  接下来4袋（i=4-7）是每天第2次投喂，减1，每袋吸收4；
  最后2袋（i=8-9）是每天第3次投喂，减2，每袋吸收3；
  总吸收量：4*5 + 4*4 + 2*3 = 42 ≥40，说明4天可行。
• 尝试mid=3天：
  总吸收量为3*5 +3*4 +3*3 +1*2=38 <40，说明3天不可行。
  因此最少天数为4，符合输出。

代码示例 #

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

total_max = sum(a)
if total_max < m:
    print(-1)
else:
    left = 1
    right = n
    ans = n
    while left <= right:
        mid = (left + right) // 2
        current = 0
        for i in range(n):
            subtract = i // mid
            current += max(a[i] - subtract, 0)
            if current >= m:  # 提前终止，优化计算
                break
        if current >= m:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    print(ans)

内容的提问来源于stack exchange，提问作者Kaiden