华为OD机试-日志限流-2022Q4 A卷-Py/Java/JS
某软件系统会在运行过程中持续产生日志，系统每天运行N单位时间，运行期间每单位时间产生的日志条数保行在数组 records中。records[i]表示第i单位时间内产生日志条数。
由于系统磁盘空间限制，每天可记录保存的日志总数上限为total条。
如果一天产生的日志总条数大于total，则需要对当天内每单位时间产生的日志条数进行限流后保存，请计算每单位时间最大可保存日志条数limit，以确保当天保存的总日志条数不超过total。
1：对于单位时间内产生日志条数不超过limit的日志全部记录保存:
2：对于单位时间内产生日志条数超过limit的日志，则只记录保存limit条日志;
如果一天产生的日志条数总和小干等于total，则不需要启动限流机制，result为-1。请返回result的最大值或者-1。
输入描述
第一行为系统某一天运行的单位时间数N.1<=N<=10^5
第二行为表示这一天每单位时间产生的日志数量的数组records，0<= records[i]<= 10^5第三行为系统一天可以保存的总日志条数total。1 <= total <= 10^9
输出描述
每单位时间内最大可保存的日志条数limit，如果不需要启动限流机制，返回-1。
示例1：输入输出示例仅供调试，后台判题数据一般不包含示例
输入
6
3 3 8 7 10 15
40
输出
9
Java 代码
import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;public class Main { public static void main(String[] args) {//处理输入Scanner in=new Scanner(System.in); int N = in.nextInt();int[] records = new int[N];long single_total = 0;for (int i = 0; i < N; i++) {records[i] = in.nextInt();single_total += records[i];}int total = in.nextInt();// 一天产生的日志总条数小于等于totalif(single_total <= total) {System.out.println(-1);return;} else {Arrays.sort(records);//二分法初始化int left = total / N;int right = records[N - 1];int result = left;while (right > left+1) {int mid = (right + left) / 2;int temp_total = 0;for (int i=0; i<N; i++){temp_total += Math.min(records[i], mid);}if (temp_total > total) {right = mid;} else if (temp_total < total) {left = mid;result = mid;} else {System.out.println(mid);return;}}System.out.println(result);return;}}}Python代码
import functools
import collections
import math
from itertools import combinations
from re import matchclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right#并查集模板
class UF:def __init__(self, n=0):self.count = nself.item = [0 for x in range(n+1)]for i in range(n):self.item[i] = idef find(self, x):if (x != self.item[x]):self.item[x] = self.find(self.item[x])return 0return xdef union_connect(self, x, y):x_item = self.find(x)y_item = self.find(y)if (x_item != y_item):self.item[y_item] = x_itemself.count-=1# 处理输入
N = int(input())
records = [int(x) for x in input().split(" ")]
total = int(input())
single_total = sum(records)find_flag = False# 一天产生的日志总条数小于等于total
if(single_total <= total):print(-1)
else:records.sort()#二分法初始化left = total / Nright = records[N - 1]result = leftwhile (right > left+1):mid = int((right + left) / 2)temp_total = 0for i in range(N):temp_total += min(records[i], mid)if (temp_total > total):right = midelif (temp_total < total):left = midresult = midelse:print(mid)find_flag = Trueif not find_flag:print(result)JS代码
function main(n, records, total) {let total_records = eval(records.join ("+"))if (total_records <= total) return -1records.sort( function (a, b){return a - b})let right = records[records.length-1]let left = Math.floor(total / n)let ans = left;while (right - left > 1) {let mid = Math.floor((right + left) / 2);let tmp = 0;for (let record of records) {tmp += Math.min(record, mid)}if (tmp > total) {right = mid;} else if (tmp < total) {left = mid;ans = mid;} else {console.log(mid)return }}console.log(ans)
}main(6,[3, 3 ,8, 7 ,10, 15],40)