淮南网站建设服务_电商办属于哪个单位_宣传链接怎么做_怎么建网站平台卖东西

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

某软件系统在运行过程中持续产生日志，系统每天运行N个单位时间，运行期间每单位时间产生的日志条数保存在数组records中。由于系统磁盘空间限制，每天可记录保存的日志总数上限为total条。

如果一天产生的日志条数大于total，则需要对当天每单位时间产生的日志条数进行限流后保存，要求计算每单位时间最大可保存日志数上限limit，使得每天保存的日志总量不超过total。

• 对于单位时间内产生日志条数超过limit的日志会被记录limit条；
• 对于单位时间内产生日志条数少于或等于limit的日志，记录全部日志。

如果一天产生的日志条数总和小于或等于total，则不需要限流，结果为-1。

任务：返回result的最大值Q或者-1。

二、输入描述

第一行为系统某一天运行的单位时间数N，1 <= N <= 10^5；
第二行为表示这一天每单位时间产生的日志条数数组records[]，0 <= records[i] <= 10^5；
第三行为系统一天可以保存的日志总数total，1 <= total <= 10^9。

三、输出描述

每单位时间内最大可保存的日志条数limit，如果不需要启动限流机制，返回-1。

四、测试用例

测试用例1：

1、输入

6
3 3 8 7 10 15
40

2、输出

9

3、说明

如题目所示，limit=9 时，保存日志总数为39 ≤40，且无法找到更大的limit满足条件。

测试用例2：

1、输入

5
1 2 3 4 5
15

2、输出

-1

3、说明

总日志数为15，等于total，无需限流，返回-1。

五、解题思路

需要在日志总量超过系统保存上限 total 的情况下，找到一个每单位时间保存日志的最大上限 limit，使得每天保存的日志总量不超过 total。

具体步骤如下：

1. 计算日志总量：首先计算数组 records 中所有日志的总和。如果总和小于或等于 total，则无需限流，直接返回 -1。
2. 二分查找：如果总和超过 total，则需要确定一个合适的 limit。我们可以采用二分查找的方法，搜索可能的 limit 值范围从 1 到 records 数组中的最大值。对于每一个中间值 mid，计算在限流 mid 的情况下，每单位时间实际保存的日志总数。如果总数小于或等于 total，则尝试增大 mid；否则，减小 mid。最终找到的最大满足条件的 limit 即为所求。
3. 优化计算：为了高效计算在某个 limit 下的保存日志总数，我们可以遍历数组，对每个记录取 min(records[i], mid) 的和。

采用二分查找的原因是它能在对数时间内快速缩小可能的 limit 范围，特别适用于本题中 N 和 records[i] 较大的情况。

六、Java算法源码

public class OdTest {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取单位时间数Nint N = scanner.nextInt();int[] records = new int[N];int maxRecord = 0; // 记录数组中的最大值long totalLogs = 0; // 记录总日志数// 读取每单位时间产生的日志数，并计算总日志数和最大日志数for (int i = 0; i < N; i++) {records[i] = scanner.nextInt();totalLogs += records[i];if (records[i] > maxRecord) {maxRecord = records[i];}}// 读取系统一天可以保存的日志总数totallong total = scanner.nextLong();// 如果总日志数小于或等于total，不需要限流if (totalLogs <= total) {System.out.println(-1);return;}// 初始化二分查找的上下界int left = 1;int right = maxRecord;int result = -1;// 二分查找最大满足条件的limitwhile (left <= right) {int mid = left + (right - left) / 2;long savedLogs = 0;// 计算在当前limit下保存的日志总数for (int i = 0; i < N; i++) {savedLogs += Math.min(records[i], mid);// 提前退出，如果已经超过totalif (savedLogs > total) {break;}}if (savedLogs <= total) {// 如果当前limit可行，尝试增大limitresult = mid;left = mid + 1;} else {// 如果当前limit不可行，尝试减小limitright = mid - 1;}}System.out.println(result);}
}

七、效果展示

1、输入

3
100000 100000 100000
200000

2、输出

66666

3、说明

总日志数=300000 >200000，需要限流。

通过二分查找，找到limit=100000时，保存日志=100000+100000+100000=300000 >200000

需要减小limit，最终limit=66666

保存日志=66666*3=199998 ≤200000

因此，输出应为66666

🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。