二分查找任务的真实解

Question

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

任务：

某公司的董事要给公司所有的经理人发奖金。分配条件必须是：

所有经理的奖金应该相等
奖金应该尽可能多
奖金必须是整数
奖金必须在每位经理的一个账户的一次交易中发出，不能使用多个账户发送单个奖金

该董事开有N个企业账户，账户上有不同数额的Cn钱，M个经理在公司工作。有必要在考虑条件的情况下找出可以发送的最大奖金数额。如果公司账户上没有足够的钱发放至少1美元的赠金，那么就没有赠金，需要提现0。

输入数据（在标准输入流中接收）第一行是用space分隔的整数N和M（1≤N≤100 000，1≤M≤100 000）然后有N行，每行有一个整数Cn(0≤Cn≤100 000 000) 不需要检查输入数据和处理输入错误的数据，验证的测试数据保证符合上述描述

输出数据（在标准输出流中预期）必须是一个整数值，最大可能的奖金

示例 1 输入：

4 6

199

453

220

601

输出： 200

示例 2 输入：

2 100

99

1

输出： 1

示例 3 输入：

2 100

98

1

输出： 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;
}

二分查找任务的真实解

Truthful solution of binary search task

java

algorithm

binary-search