二分查找求解最大等额奖金题代码Wrong Answer排查求助

代码问题排查与修复方案 #

存在的核心问题 #

• 整数溢出错误：
  1. 全局变量sum定义为int类型，当1e5个账户每个余额1e8时，总余额可达1e13，远超过int的最大上限（约2e9），溢出后sum值为负数或错误值，直接导致二分上限计算错误。
  2. 原isNear方法中计数变量managerCnt为int类型，当奖金金额较小时，单个账户可拆分的奖金份数最多可达1e8，累计后总份数会超过int上限，溢出后判断逻辑完全错误。
• 二分逻辑冗余不稳定：
  自定义的二分跳转逻辑需要重复调用两次判断方法，不仅增加了一倍的遍历开销，边界判断逻辑在极端场景下容易触发死循环或提前跳出错误，常规的二分查找模板更简洁可靠。
• 输入读取效率低：
  使用Scanner.nextLine逐行读取1e5条数据速度较慢，严格超时限制的测试用例可能无法通过。

修复后可通过全部用例的代码 #

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int managerCount;
    private static int[] accountMoney;
    private static long sum = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int accountCount = Integer.parseInt(firstLine[0]);
        managerCount = Integer.parseInt(firstLine[1]);
        accountMoney = new int[accountCount];

        for (int i = 0; i < accountCount; i++) {
            accountMoney[i] = Integer.parseInt(br.readLine());
            sum += accountMoney[i];
        }
        
        // 总和不够每人1元直接返回0
        if (sum < managerCount) {
            System.out.println(0);
            return;
        }
        System.out.println(getValue());
    }

    private static boolean check(int salary) {
        long cnt = 0;
        for (int v : accountMoney) {
            cnt += v / salary;
            // 提前退出，不用遍历全部账户优化性能
            if (cnt >= managerCount) {
                return true;
            }
        }
        return cnt >= managerCount;
    }

    private static int getValue() {
        int left = 1;
        int right = (int) (sum / managerCount);
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

内容的提问来源于stack exchange，提问作者strelchm