【二分查找】2023A-开放日活动

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3302

题目描述

某部门开展 Family Day 开放日活动，其中有个从桶里取球的游戏，游戏规则如下：有 N 个容量一样的小桶等距排开，且每个小桶都默认装了数量不等的小球，每个小桶装的小球数量记录在数组bucketBallNums中，游戏开始时，要求所有桶的小球总数不能超过SUM，如果小球总数超过SUM，则需对所有的小桶统一设置一个尽可能大的容量最大值maxCapacity，并需将超过容量最大值的小球拿出来，直至所有小桶里的小球数量均不大于maxCapacity。

请您根据输入的数据，计算出尽可能大的容量最大值maxCapacity，并输出从每个小桶里拿出的小球数量。

限制规则一 如果所有小桶的小球总和小于SUM，则无需设置容量值，并且无需从小桶中拿球出来，返回结果[]

限制规则二 如果所有小桶的小球总和大于SUM，则需设置一个尽可能大的容量最大值maxCapacity，并且需从小桶中拿球出来，返回从每个小桶拿出的小球数量组成的数组

输入

第一行输入2个正整数，数字之间使用空格隔开，其中第一个数字表示SUM，第二个数字表示bucketBallNums数组长度； 第二行输入N个正整数，数字之间使用空格隔开，表示bucketBallNums的每一项。

输出

一个数组。

示例一

输入

14 7
2 3 2 5 5 1 4

输出

[0,1,0,3,3,0,2]

说明

小球总数为22，SUM = 14，超出范围了，需从小桶取球。

• maxCapacity = 1，取出球后，1 1 1 1 1 1 1， 桶里剩余小球总和为7，远小于14
• maxCapacity = 2，取出球后，2 2 2 2 2 1 2，桶里剩余小球总和为13，小于14
• maxCapacity = 3，取出球后，2 3 2 3 3 1 3，桶里剩余小球总和为16，大于14

因此选择maxCapacity为2 ，每个小桶小球数量大于 2 的都需要拿出来。

示例二

输入

3 3
1 2 3

输出

[0,1,2]

说明

小球总数为6，SUM = 3，超出范围了，需从小桶取球。

取maxCapacity = 1，则小球总数为 3，从 0 号桶取出 0 个球，从 1 号桶取出 1 个球，从 2 号桶取出 2 个球。故输出[0, 1, 2]。

示例三

输入

6 2
3 2

输出

[]

说明

小球总数为5，SUM = 6，无需从小桶取球；

备注

1 <= bucketBallNums[i] <= 10^9` `1 <= bucketBallNums.length = N <= 10^5` `1 <= maxCapacity <= 10^9` `1 <= SUM <= 10^9

解题思路

二段性分析

考虑容量最大值maxCapacity与剩余小球数量之间的关系

• 容量最大值maxCapacity越大的时候，在原列表bucketBallNums中需要取出的小球数越少，剩余小球数量越多。当取到最值maxCapacity = max(bucketBallNums)时，则无需取出任何小球，bucketBallNums等同于初始状态，必然大于SUM。
• 容量最大值maxCapacity越小的时候，在原列表bucketBallNums中需要取出的小球数越多，剩余小球数量越少。当取到最值maxCapacity = 0时，则需取出所有小球，此时剩余小球数量为0，必定小于等于SUM。
• 对于在区间[0, max(bucketBallNums)]之间取值的容量最大值maxCapacity而言，一定存在一个值ans，使得
  • 当maxCapacity ∈ [0, ans]时，剩余球数小于等于SUM
  • 当maxCapacity ∈ (ans, max(bucketBallNums)]时，剩余球数大于SUM
  • 这体现了这个问题的二段性，ans是我们需要的答案，而ans的寻找就可以用二分查找来完成。

边界情况的考虑

• 如果sum(bucketBallNums) < SUM，那么无需设置容量最大值maxCapacity，直接输出空列表[]。这种情况需要单独讨论。

子问题分析

对于二分查找过程中得到的每一个容量最大值maxCapacity = mid，我们都要计算得到原数组bucketBallNums取出小球后的剩余球数。对于bucketBallNums中每一个元素num，当

• bucketBallNums[i] = num < maxCapacity时，在bucketBallNums[i]中无需取出任何小球，故求和时需要应该用num进行求和
• bucketBallNums[i] = num ≥ maxCapacity时，在bucketBallNums[i]中需要取出若干球，直到num变为maxCapacity，故求和时需要应该用maxCapacity进行求和

上述逻辑整理为代码即构建 getSumWithMaxCap(maxCapacity, bucketBallNums)函数

def getSumWithMaxCap(maxCapacity, bucketBallNums):
    return sum(min(num, maxCapacity) for num in bucketBallNums)

代码

Python

# 题目：2023Q1A-开放日活动
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：二分查找
# 代码看不懂的地方，请直接在群上提问


# 二分查找过程中的辅助函数，用于检查在设置了容量最大值maxCapacity的条件下
# bucketBallNums列表取出小球后，剩余的总球数
def getSumWithMaxCap(maxCapacity, bucketBallNums):
    # 如果原来bucketBallNums中的元素num小于maxCapacity，则无需取出，保留num
    # 如果原来bucketBallNums中的元素num大于maxCapacity，则需要取出若干球，直到num变为maxCapacity
    # 故设置了容量最大值maxCapacity后，每一个桶中的球数为min(num, maxCapacity)，再求和即可
    return sum(min(num, maxCapacity) for num in bucketBallNums)


SUM, n = map(int, input().split())
bucketBallNums = list(map(int, input().split()))


# 如果初始列表bucketBallNums中的小球总数小于给定的总数SUM
# 无需设置容量最大值maxCapacity，直接输出一个列表
if sum(bucketBallNums) < SUM:
    print([])
# 否则需要设置容量最大值maxCapacity，进行二分查找
else:
    # 如果left取值为0，那么需要取出所有小球，此时剩余小球数量为0，必定小于等于SUM
    # 故左闭区间left取1
    # 如果right取值为bucketBallNums中的最大值，则无需取出任何小球
    # bucketBallNums等同于初始状态，必然大于SUM
    # maxCapacity = max(bucketBallNums)一定不是正确的最大容量值，
    # 故右开区间right取max(bucketBallNums)+1
    left, right = 1, max(bucketBallNums)+1

    # 左闭右开区间，退出循环时存在 left = right = mid
    # 循环不变量为left < right
    while left < right:
        mid = (left + right) // 2
        # 设置的maxCapacity使得bucketBallNums中的元素和大于SUM，说明移除的小球太少
        # 最大容量值maxCapacity设置得太大，right需要左移
        if getSumWithMaxCap(mid, bucketBallNums) > SUM:
            right = mid
        # 设置的maxCapacity使得bucketBallNums中的元素和小于等于SUM，说明移除的小球太多
        # 最大容量值说明maxCapacity设置得太小，left需要右移
        else:
            left = mid + 1

    # 跳出二分查找的while循环时，存在 left = right 使得
    # getSumWithMaxCap(left, bucketBallNums) > SUM 是恰好满足的最小的maxCapacity
    # 故left-1是使得getSumWithMaxCap(left, bucketBallNums) <= SUM恰好满足的最大maxCapacity
    maxCapacity = left-1

    # 构建最终要输出的答案列表，表示在取了maxCapacity的前提下，bucketBallNums列表中每一个桶要取出多少小球
    ans = [0 if num < maxCapacity else num - maxCapacity for num in bucketBallNums]

    print(ans)

Java

import java.util.*;

public class Main {
    public static int getSumWithMaxCap(int maxCapacity, List<Integer> bucketBallNums) {
        int sum = 0;
        for (int num : bucketBallNums) {
            sum += Math.min(num, maxCapacity);
        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int SUM = scanner.nextInt();
        int n = scanner.nextInt();
        List<Integer> bucketBallNums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            bucketBallNums.add(scanner.nextInt());
        }

        if (bucketBallNums.stream().mapToInt(Integer::intValue).sum() < SUM) {
            System.out.println(Collections.emptyList());
        } else {
            int left = 1;
            int right = Collections.max(bucketBallNums) + 1;

            while (left < right) {
                int mid = (left + right) / 2;
                if (getSumWithMaxCap(mid, bucketBallNums) > SUM) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            int maxCapacity = left - 1;
            List<Integer> ans = new ArrayList<>();
            for (int num : bucketBallNums) {
                ans.add(num < maxCapacity ? 0 : num - maxCapacity);
            }

            System.out.println(ans);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int getSumWithMaxCap(int maxCapacity, const vector<int>& bucketBallNums) {
    int sum = 0;
    for (int num : bucketBallNums) {
        sum += min(num, maxCapacity);
    }
    return sum;
}

int main() {
    int SUM, n;
    cin >> SUM >> n;
    vector<int> bucketBallNums(n);
    for (int i = 0; i < n; i++) {
        cin >> bucketBallNums[i];
    }

    if (accumulate(bucketBallNums.begin(), bucketBallNums.end(), 0) < SUM) {
        cout << "[]" << endl;
    } else {
        int left = 1;
        int right = *max_element(bucketBallNums.begin(), bucketBallNums.end()) + 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (getSumWithMaxCap(mid, bucketBallNums) > SUM) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        int maxCapacity = left - 1;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = (bucketBallNums[i] < maxCapacity) ? 0 : (bucketBallNums[i] - maxCapacity);
        }

        cout << "[";
        for (int i = 0; i < n; i++) {
            cout << ans[i];
            if (i != n - 1) {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }

    return 0;
}

时空复杂度

时间复杂度：O(nlogC)。

• C = max(bucketBallNums)为小球数量的最大值，n为bucketBallNums数组的长度。
• 在[1, max(bucketBallNums)]这个搜索区间中进行容量最大值maxCapacity的二分查找，时间复杂度为O(logC)。
• 每一个容量最大值maxCapacity所对应的剩余小球数量总和计算，均需要遍历整个bucketBallNums数组，故单次getSumWithMaxCap(maxCapacity, bucketBallNums)函数所需的时间复杂度为O(n)。
• 故总时间复杂度为O(n) × O(logC) = O(nlogC)

空间复杂度：O(1)。