题面描述

某部门开展 Family Day 开放日活动，其中有个从桶里取球的游戏，游戏规则如下：

• 有 N 个容量一样的小桶等距排开，且每个小桶都默认装了数量不等的小球，每个小桶装的小球数量记录在数组 bucketBallNums 中。
• 游戏开始时，要求所有桶的小球总数不能超过 SUM，如果小球总数超过 SUM，则需对所有的小桶统一设置一个容量最大值 maxCapacity，并需将超过容量最大值的小球拿出来，直至小桶里的小球数量小于 maxCapacity。
• 如果所有小桶的小球总和小于 SUM，则无需设置容量值 maxCapacity，并且无需从小桶中拿球出来，返回结果 []。
• 如果所有小桶的小球总和大于 SUM，则需设置容量最大值 maxCapacity，并且需从小桶中拿球出来，返回从每个小桶拿出的小球数量组成的数组。

思路

1. 计算总和：首先计算所有小桶中小球的总和 total。
2. 判断是否需要取球：如果 total <= SUM，则直接返回空数组 []。
3. 确定 maxCapacity：如果 total > SUM，则需要找到一个合适的 maxCapacity，使得所有小桶中小球的数量不超过 maxCapacity，并且所有小桶中小球的总和不超过 SUM。
4. 计算每个小桶需要取出的球数：对于每个小桶，如果小球数量大于 maxCapacity，则取出多余的小球。

cpp

#include <bits/stdc++.h>
 
using namespace std;
 
int sum, n;
vector<int> bucketBallNums;
 
bool check(int maxCapacity) {
    long remain = 0;
 
    for (int i = 0; i < n; i++) {
        // 若桶中小球数量超出 maxCapacity，则只能保留 maxCapacity 个
        remain += min(bucketBallNums[i], maxCapacity);
    }
 
    return remain <= sum;
}
 
int main() {
    cin >> sum >> n;
 
    bucketBallNums = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> bucketBallNums[i];
    }
 
    int bucketBallNums_max = 0;
    long bucketBallNums_sum = 0;
 
    for (int i = 0; i < n; i++) {
        bucketBallNums_max = max(bucketBallNums_max, bucketBallNums[i]);
        bucketBallNums_sum += bucketBallNums[i];
    }
 
    // 所有小桶的小球总和小于 SUM，则无需设置容量值 maxCapacity，并且无需从小桶中拿球出来，返回结果[]
    if (bucketBallNums_sum <= sum) {
        cout << "[]" << endl;
        return 0;
    }
 
    // 二分范围
    int low = 0;
    int high = bucketBallNums_max;
 
    // 记录最优解
    int limit = 0;
 
    // 二分
    while (low <= high) {
        int mid = (high - low) / 2 + low;
 
        // 限制每个桶mid容量，看桶中剩余球数量是否小于等于sum
        if (check(mid)) {
            // 若是，则mid是一个可能解，但不一定是最优解
            limit = mid;
            // 继续尝试更大限制，即提高下限
            low = mid + 1;
        } else {
            // 若不是，则mid限制下，所有桶剩余球数量任然大于sum，因此应该尝试更小限制，即压低上限
            high = mid - 1;
        }
    }
 
    // 输出打印
    cout << "[";
 
    for (int i = 0; i < n; i++) {
        // 取出超出部分后，各个桶中剩余球数量
        cout << bucketBallNums[i] - min(bucketBallNums[i], limit);
 
        if (i < n - 1) {
            cout << ",";
        }
    }
 
    cout << "]";
 
    return 0;
}

python

# 输入获取
SUM, N = map(int, input().split())
bucketBallNums = list(map(int, input().split()))
 
 
def check(maxCapacity):
    remain = 0
 
    for i in range(N):
        # 若桶中小球数量超出 maxCapacity，则只能保留 maxCapacity 个
        remain += min(bucketBallNums[i], maxCapacity)
 
    return remain <= SUM
 
 
def solution():
    # 所有小桶的小球总和小于 SUM，则无需设置容量值 maxCapacity，并且无需从小桶中拿球出来，返回结果[]
    if sum(bucketBallNums) <= SUM:
        return "[]"
 
    # 二分范围
    low = 0
    high = max(bucketBallNums)
 
    # 记录最优解
    limit = 0
 
    # 二分
    while low <= high:
        mid = (low + high) // 2
 
        # 限制每个桶mid容量，看桶中剩余球数量是否小于等于sum
        if check(mid):
            # 若是，则mid是一个可能解，但不一定是最优解
            limit = mid
            # 继续尝试更大限制，即提高下限
            low = mid + 1
        else:
            # 若不是，则mid限制下，所有桶剩余球数量任然大于sum，因此应该尝试更小限制，即压低上限
            high = mid - 1
 
    # 取出超出部分后，各个桶中剩余球数量
    res = list(map(lambda num: str(num - min(num, limit)), bucketBallNums))
 
    return f"[{",".join(res)}]"
 
 
# 输出打印
print(solution())

java

import java.util.Scanner;
import java.util.StringJoiner;
 
public class Main {
    public static int sum, n;
    public static int[] bucketBallNums;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        sum = sc.nextInt();
        n = sc.nextInt();
 
        bucketBallNums = new int[n];
        for (int i = 0; i < n; i++) {
            bucketBallNums[i] = sc.nextInt();
        }
 
        System.out.println(solution());
    }
 
    public static String solution() {
        int bucketBallNums_max = 0;
        long bucketBallNums_sum = 0;
 
        for (int i = 0; i < n; i++) {
            bucketBallNums_max = Math.max(bucketBallNums_max, bucketBallNums[i]);
            bucketBallNums_sum += bucketBallNums[i];
        }
 
        // 所有小桶的小球总和小于 SUM，则无需设置容量值 maxCapacity，并且无需从小桶中拿球出来，返回结果[]
        if (bucketBallNums_sum <= sum) {
            return "[]";
        }
 
        // 二分范围
        int min = 0;
        int max = bucketBallNums_max;
 
        // 记录最优解
        int limit = 0;
 
        // 二分
        while (min <= max) {
            int mid = (max - min) / 2 + min;
 
            // 限制每个桶mid容量，看桶中剩余球数量是否小于等于sum
            if (check(mid)) {
                // 若是，则mid是一个可能解，但不一定是最优解
                limit = mid;
                // 继续尝试更大限制，即提高下限
                min = mid + 1;
            } else {
                // 若不是，则mid限制下，所有桶剩余球数量任然大于sum，因此应该尝试更小限制，即压低上限
                max = mid - 1;
            }
        }
 
        StringJoiner sj = new StringJoiner(",", "[", "]");
 
        for (int i = 0; i < n; i++) {
            // 取出超出部分后，各个桶中剩余球数量
            bucketBallNums[i] -= Math.min(bucketBallNums[i], limit);
            sj.add(bucketBallNums[i] + "");
        }
 
        return sj.toString();
    }
 
    public static boolean check(int maxCapacity) {
        long remain = 0;
 
        for (int i = 0; i < n; i++) {
            // 若桶中小球数量超出 maxCapacity，则只能保留 maxCapacity 个
            remain += Math.min(bucketBallNums[i], maxCapacity);
        }
 
        return remain <= sum;
    }
}

题目内容

某部门开展 $Family Day$ 开放日活动，其中有个从桶里取球的游戏，游戏规则如下：

有 $N$ 个容量一样的小桶等距排开，且每个小桶都默认装了数量不等的小球，每个小桶装的小球数量记录在数组 $bucketBallNums$ 中，

游戏开始时，要求所有桶的小球总数不能超过 $SUM$，如果小球总数超过 $SUM$，则需对所有的小桶统一设置一个容量最大值 $maxCapacity$，并需将超过容量最大值的小球拿出来，直至小桶里的小球数量小于 $maxCapacity$。

请您根据输入的数据，计算从每个小桶里拿出的小球数量？

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

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

输入描述

第一行输入 $2$ 个正整数，数字之间使用空格隔开，其中：

• 第一个数字表示 $SUM$

• 第二个数字表示 $bucketBallNums$ 数组长度

第二行输入 $N$ 个正整数，数字之间使用空格隔开，表示 $bucketBallNums$ 的每一项

输出描述

从每个小桶里拿出的小球数量，并使用一维数组表示

备注

• $1 ≤ bucketBallNums[i] ≤ 10^9$

• $1 ≤ bucketBallNums.length = N ≤ 10^5$

• $1 ≤ maxCapacity ≤ 10^9$

• $1 ≤ SUM ≤ 10^9$

样例1

输入

14 7
2 3 2 5 5 1 4

输出

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

说明

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

$maxCapacity = 1$，取出球后，桶里剩余小球总和为 $7$，远小于 $14$

$maxCapacity = 2$，取出球后，桶里剩余小球总和为 $13$，

$maxCapacity = 3$，取出球后，桶里剩余小球总和为 $16$，大于 $14$

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

样例2

输入

3 3
1 2 3

输出

[0,1,2]

说明

小球总数为 $6$，$SUM = 3$，超出范围了，需从小桶中取球，$maxCapacity = 1$，则小球总数为 $3$，从 $1$ 号桶取 $0$ 个球，$2$ 号桶取 $1$ 个球，$3$ 号桶取 $2$ 个球；

样例3

输入

6 2
3 2

输出

[]

说明

小球总数为 $5$，$SUM = 6$，在范围内，无需从小桶取球；