2024-07-09 明明的随机数 && 购物单

MarshioAbout 4 min

明明的随机数open in new window

明明生成了 N个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。

输入描述：第一行先输入随机整数的个数 N 。接下来的 N 行每行输入一个整数，代表明明生成的随机数。

输入:
4
1
2
2
3
输出:
1
2
3

解题思路

简单说下思路，题目限定了输入数字的范围，且一个数字只会出现一次，所以我们使用boolean[] arr = new boolean[501]来存储数字是否出现过，然后从前到后输出即可。

亮点

boolean数组，节省空间开销
使用 BufferedReader 读取控制台输入，减少时间开销
时间复杂度为 O(n)
空间复杂度为 O(n)

实现

public class Test005 {
    /**
     * 明明生成了 N个1到500之间的随机整数。请你删去其中重复的数字，
     * 即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。
     *
     * @param args 输入参数
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        boolean[] arr = new boolean[501];
        int n = in.nextInt();
        while (n-- > 0) {
            // 注意 while 处理多个 case
            arr[in.nextInt()] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 500; i++) {
            if (arr[i]) {
                sb.append(i).append("\n");
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb);
    }

    public void test() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        boolean[] flag = new boolean[501];
        while (n-- > 0) {
            int tmp = Integer.parseInt(br.readLine());
            flag[tmp] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 500; i++) {
            if (flag[i]) {
                sb.append(i).append("\n");
            }
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1));
    }
}

发现

牛客提交运行时，其执行时间会根据各种环境因素的影响而改变，比如，我用Java排名第一的代码执行，他执行时用了 8ms，我用同样的代码提交执行了 16 ms。

所以这个排行仅作参考就好了。

购物单open in new window

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。

每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。

王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。

他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。

满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第 i 件物品的价格为 v[i]，重要度为 w[i]，共选中了 k件物品，编号依次为 j1, j2, ..., jk,则满意度为： ${v[j1] * w[j1] + v[j2] * w[j2] + ... + v[jk] * w[jk]}$ （其中 * 为乘号），请你帮助王强计算可获得的最大的满意度。

输入描述

输入的第 1 行，为两个正整数N，m，用一个空格隔开：

（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q

（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）