华为OD机试-开放日活动-2022Q4 A卷-Py/Java/JS

某部门开展Family Day开放日活动，其中有个从桶里取球的游戏，游戏规则如下:有N个容量一样的小桶等距排开，且每个小桶都默认装了数量不等的小球，
每个小桶装的小球数量记录在数组 bucketBallNums 中,游戏开始时，要求所有桶的小球总数不能超过 SUM，
如果小球总数超过 SUM，则需对所有的小桶统一设置一个容量最大值 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，取出球后，桶里剩余小球总和为7，远小于 14 maxCapacity=2，取出球后，桶里剩余小球总和为13
maxCapacity=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个球;

示例三

输入
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

Java 代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;
import java.math.BigInteger;
import java.util.stream.IntStream;class Main {public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);int sum = in.nextInt();int nums = in.nextInt();int[] balls = new int[nums];int[] org_balls = new int[nums];for (int i = 0; i < nums; i++) {balls[i] = in.nextInt();org_balls[i] = balls[i];}int total =  Arrays.stream(balls).sum();if (total <= sum) {System.out.println("[]");return;}Arrays.sort(balls);//二分法初始化int left = sum / nums;int right = balls[nums - 1];int[] result = new int[nums];for (int i = 0; i < nums; i++) {result[i] = org_balls[i] > left ? org_balls[i] - left : 0;}while (right > left+1){int mid = (right + left) / 2;int[] tmp = new int[nums];int temp_total = total;for (int i = 0; i < balls.length; i++) {int r = org_balls[i] > mid? org_balls[i] - mid: 0;temp_total -= r;tmp[i] = r;}if (temp_total > sum)right = mid;else if (temp_total < sum){left = mid;result = tmp;}else{result = tmp;break;}}System.out.println(Arrays.toString(result));}}

Python代码

import functools
import collections
import math
from itertools import combinations
from re import match# 处理输入
params = [int(x) for x in input().split(" ")]
total = params[0]
N = params[1]
balls = [int(x) for x in input().split(" ")]
origin_balls = []
for i in balls:origin_balls.append(i)
single_total = sum(balls)if(single_total <= total):print([])
else:#二分法初始化left = int(total / N)right = max(balls)result = [x - left if x > left else 0 for x in origin_balls]while (right > left+1):mid = int((right + left) / 2)temp = []for i in range(N):if(balls[i] > mid):temp.append(origin_balls[i] - mid)else:temp.append(0)if (single_total - sum(temp)>total):right = midelif (single_total -sum(temp)<total):left = midresult = tempelse:result = tempbreakprint(result)

JS代码

function main(sum, nums, balls ) {let total = eval(balls.join("+"))if (total <= sum) {console.log("[]")return}let org_balls = []for (let i=0;i<nums;i++){org_balls.push(balls[i])}balls.sort()//二分法初始化let left = sum / nums;let right = balls[nums - 1]let result = new Array(nums)for (let i = 0; i < nums; i++) {result[i] = org_balls[i] > left ? org_balls[i] - left : 0;}while (right > left+1){let mid = (right + left) / 2let tmp = new Array(nums)let temp_total = totalfor (let i = 0; i < balls.length; i++) {let r = org_balls[i] > mid? org_balls[i] - mid : 0;temp_total -= r;tmp[i] = r;}if (temp_total > sum)right = mid;else if (temp_total < sum){left = mid;result = tmp;}else{result = tmp;break;}}console.log(result)}main(3,3,[2,3,1])