二进制搜索任务的java真实解决方案

Question

我不能解决基于计算机基础科学的任务。起初，我用线性递减法进行求解，但这需要花费大量的时间，而且解决方案没有通过任务平台的测试。然后我将代码重构为二进制搜索。一切都很好，但这个解决方案没有通过测试——其中一个答案是错误的。未显示错误答案的全部原因，仅显示“错误答案”信息。请帮助adwise我的代码中的逻辑有什么问题

任务是：

某公司的董事将把奖金分配给该公司的所有经理。分配条件必须是：

1. 所有经理的奖金应该相等
2. 奖金应该尽可能高
3. 奖金必须是整数
4. 奖金必须在一笔交易中从每个经理的一个帐户中发放，而不使用多个帐户发送单个奖金

该董事开设了N个公司账户，账户上有不同金额的Cn资金，M名经理在该公司工作。考虑到各种情况，有必要找出可以发放的奖金的最大金额。如果公司账户上没有足够的钱来发放至少1美元的奖金，那么就没有奖金，您需要提取0美元

输入数据（在标准输入流中接收） 第一行是由一个空格（1）分隔的整数N和M≤N≤100 000, 1≤M≤100 000) 然后有N行，每行有一个整数Cn（0）≤Cn≤100 000 000) 无需检查输入数据并在输入时处理不正确的数据，用于验证的测试数据保证符合上述说明

输出数据（标准输出流中需要）必须是一个整数值，即最大可能的加值

示例1输入：

4.6

199

453

220

601

输出：200

示例2输入：

2100

99

一,

输出：1

示例3输入：

2100

98

一,

输出：0

我的解决方案：

    import java.util.Scanner;
    
    public class Main {
        private static int managerCount;
        private static int[] accountMoney;
        private static int sum = 0;
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String firstLine = sc.nextLine();
            String[] firstLineArray = firstLine.split(" ");
    
            int accountCount = Integer.parseInt(firstLineArray[0]);
            accountMoney = new int[accountCount];
            managerCount = Integer.parseInt(firstLineArray[1]);
    
            for (int i = 0; i < accountCount; i++) {
                accountMoney[i] = Integer.parseInt(sc.nextLine());
                sum += accountMoney[i];
            }
            System.out.println(getValue());
        }
    
        private static boolean isNear(int salary, int managerCnt) {
            for (Integer v : accountMoney) {
                int totalSum = v;
                if (totalSum >= salary && managerCnt > 0) {
                    managerCnt -= totalSum / salary;
                }
            }
            return managerCnt <= 0;
        }
    
        private static int getValue() {
            int highLimit = sum / managerCount;
            int halfPart = highLimit;
            int lowLimit = 0;
            boolean isNear;
            boolean isNextNear;
            while (halfPart > 0) {
                isNear = isNear(halfPart, managerCount);
                isNextNear = isNear(halfPart + 1, managerCount);
                if (isNear && !isNextNear) {
                    break;
                }
                if (lowLimit == highLimit) {
                    halfPart = halfPart == lowLimit ? 0 : lowLimit;
                } else if (isNear) {
                    lowLimit = halfPart + 1;
                    halfPart = (lowLimit + highLimit) / 2;
                } else if (!isNextNear) {
                    highLimit = halfPart - 1;
                    halfPart = (lowLimit + highLimit) / 2;
                }
            }
            return halfPart;
        }
}

Answer 1

您可能需要修改如何实现binary search：

getValue函数应更改为：

private static int getValue() {
    int highLimit = sum / managerCount;
    int lowLimit = 0;
    int halfPart;
    boolean isNear;
    while (highLimit > lowLimit) {
        halfPart = lowLimit + (highLimit - lowLimit + 1) / 2;
        if (isNear(halfPart, managerCount)) {
            lowLimit = halfPart;
        } else {
            highLimit = halfPart - 1;
        }
    }
    return lowLimit;
}