时间戳

首页 > 解决方案 > Google Kickstart 2020 年 A 轮分配

java - Google Kickstart 2020 年 A 轮分配

问题描述

问题 有 N 栋房屋待售。房子i-th要花艾美元才能买到。你有 B 美元的预算要花。

最多可以买多少套房子？

时间限制：每个测试集 15 秒。

内存限制：1GB。
1 ≤ T ≤ 100.
1 ≤ B ≤ 105.
1 ≤ Ai ≤ 1000, 对于所有i.

测试集 1：
1 ≤ N ≤ 100.

测试集 2：
1 ≤ N ≤ 10^5.

我试图首先对房屋的价格进行排序，然后用我们数组中剩下的最低价格的房子减去预算，直到用完所有预算。界面说我有一个运行时错误，但是我在 ide 上运行的示例测试用例并没有给出这样的东西。我能做些什么来解决这个运行时错误？

import java.util.Scanner;
import java.util.Arrays;

class Houses{

    public static void main(String []args){

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int N, B;
        int []arr;
        int []result = new int[T];

        for(int i=0; i<T; i++){
            N = sc.nextInt();
            B = sc.nextInt();
            arr = new int[N];
        
            for(int j=0; j<N; j++)
                arr[j] = sc.nextInt();
        
            int houses=0, k=0;
            Arrays.sort(arr);
            while(B>=arr[k]){
               B = B-arr[k];
               k++;
               houses++;
            }
            result[i] = houses;
        }
        for(int i=0; i<T; i++){
            System.out.println("Case #" + (i+1) + ": " + result[i]);
        }
    }
}

标签： javaruntime-error

解决方案

我重新编写了您的算法，以使其更易于测试和更易于调试。

我可以给你多个提示：

  • 如果您想运行测试，请尽可能将它们自动化。我什至想删除“要运行的测试数量”，但将其保留，以便您选择
  • 将您的算法拆分为方法，以便您可以更轻松地定位问题并运行不同的测试
  • 使用 IDE 的代码格式化功能（推荐保存时格式化，使用自定义格式化设置）。这将清除许多视觉问题，因此您可以更轻松地查看错误
  • 为变量使用正确的名称。对于不能一遍又一遍地编写长变量名的数学家来说，使用单个字母是一个坏习惯。在编程中，拥有好名字更为重要，因此即使它变得复杂或出现错误，您也不会迷失方向
  • 对于固定值，使用常量（public static final）
  • 我在代码中包含了很多消息/打印，以展示正在发生的事情。这使得代码执行非常慢，所以为了提交任务，我会把它们全部注释掉
  • 真正的测试将使用 JUnit 完成，无需打印。如果完成了一些打印，就会使用 Loggers。

这就是我的部分，享受：

package stackoverflow;

import java.util.Arrays;
import java.util.Scanner;

class Houses {

    static public final int BUDGET_MIN  = 1;
    static public final int BUDGET_MAX  = 105;

    static public final int HOUSE_PRICE_MIN = 1;
    static public final int HOUSE_PRICE_MAX = 1000;

    static public final int AMOUNT_HOUSES_MIN   = 1;
    static public final int AMOUNT_HOUSES_MAX   = 100;



    static public int prepareBuy() {
        final int numberOfHouses = getRandomIn(AMOUNT_HOUSES_MIN, AMOUNT_HOUSES_MAX);
        final int[] prices = new int[numberOfHouses];
        for (int i = 0; i < prices.length; i++) {
            final int price = getRandomIn(HOUSE_PRICE_MIN, HOUSE_PRICE_MAX);
            prices[i] = price;
        }
        final int availableBudget = getRandomIn(BUDGET_MIN, BUDGET_MAX);
        final int result = buyHouses(availableBudget, prices);
        return result;
    }

    static private int getRandomIn(final int pMin, final int pMax) {
        return (int) (pMin + Math.random() * (pMax - pMin + 1));
    }



    static public int buyHouses(final int pAvailableBudget, final int[] pHousePrices) {
        System.out.println("\t\tBudget (B):\t" + pAvailableBudget);
        System.out.println("\t\tHouses (N):\t" + pHousePrices.length);
        System.out.print("\t\tHouses for sale:\t");
        for (int i = 0; i < pHousePrices.length; i++) {
            final int price = pHousePrices[i];
            System.out.print(i + ":" + price + " ");
        }
        System.out.println();

        Arrays.sort(pHousePrices);
        System.out.print("\t\tHouses sorted:\t\t");
        for (int i = 0; i < pHousePrices.length; i++) {
            final int price = pHousePrices[i];
            System.out.print(i + ":" + price + " ");
        }
        System.out.println();

        int availableBudget = pAvailableBudget;
        int houses = 0, k = 0;
        while (pAvailableBudget >= pHousePrices[k]) {
            System.out.println("\t\tBuing house for " + pHousePrices[k] + "...");
            availableBudget = availableBudget - pHousePrices[k];
            k++;
            houses++;
            System.out.println("\t\t\tHouses bought: " + houses);
            System.out.println("\t\t\tBudget left: " + availableBudget);
        }
        final int result = houses;
        return result;
    }


    public static void main(final String[] args) {
        System.out.print("Enter number of tests: ");
        try (final Scanner sc = new Scanner(System.in);) {
            final int tests = sc.nextInt();
            System.out.println();

            final int[] results = new int[tests];

            System.out.println("Running " + tests + " tests...");
            for (int i = 0; i < tests; i++) {
                System.out.println("\tTest #" + (i + 1) + ":\t");
                final int housesBought = prepareBuy();
                results[i] = housesBought;
                System.out.println("\tTest #" + (i + 1) + " result: Bought " + housesBought + " houses\n");
            }
        }

        System.out.println("\nAll tests complete.");
    }

}

推荐阅读