按比例切分组合数值(洛谷P1008、P1618题解,Java语言描述)

P1008题目要求

P1008题目链接
按比例切分组合数值(洛谷P1008、P1618题解,Java语言描述)

P1618题目要求

P1618题目链接
按比例切分组合数值(洛谷P1008、P1618题解,Java语言描述)

分析

P1618是P1008的增强版,使得一个水题没有那么水了,不过还是挺简单的。

其实judge()函数的话,两题可以共用,就是判断一下是不是“槽位已满”而已。如果还有坑位就占上,就这么个思路。

main()里的基本流程的话,其实没什么特别的算法,暴力枚举就行。
第一题的话由于是1:2:3,所以下限也就123,上限也就333,在里面遍历能缩小范围。
第二题的话由于是A:B:C,所以不能自设上下限,从1~999即可,极限暴力就好啦,但是必须在A,B,C那里设限,全部要在100 ~ 999之间,这个很重要,在judge()之前保证数据范围可以避免RE(数组越界)。

P1618第一次提交WA了一个样例:
按比例切分组合数值(洛谷P1008、P1618题解,Java语言描述)

我获取了测试数据5:
in
123 456 789
out
123 456 789

其实就是上面说的问题,不应该在for循环设限,而是应该在judge()之前设限。

P1008~AC代码(Java语言描述)

public class Main {

    private static byte[] arr = new byte[9];

    public static void main(String[] args) {
        for (int i = 123; i < 333; i++) {
            arr = new byte[9];
            int two = 2*i, three = 3*i;
            if (judge(i) && judge(two) && judge(three)) {
                System.out.println(i + " " + two + " " + three);
            }
        }
    }

    private static boolean judge(int i) {
        int a = i / 100;
        int b = (i % 100) / 10;
        int c = i - a*100 - b*10;
        if (b == 0 || c == 0 || a == b || a == c || b == c || arr[a-1] == 1 || arr[b-1] == 1 || arr[c-1] == 1) {
            return false;
        }
        arr[a-1] = arr[b-1] = arr[c-1] = 1;
        return true;
    }
    
}

P1618~AC代码(Java语言描述)

import java.util.Scanner;

public class Main {

    private static byte[] arr = new byte[9];

    private static boolean judge(int i) {
        int a = i / 100;
        int b = (i % 100) / 10;
        int c = i - a*100 - b*10;
        if (b == 0 || c == 0 || a == b || a == c || b == c || arr[a-1] == 1 || arr[b-1] == 1 || arr[c-1] == 1) {
            return false;
        }
        arr[a-1] = arr[b-1] = arr[c-1] = 1;
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt();
        scanner.close();
        boolean flag = false;
        for (int i = 1; i < 1000; i++) {
            arr = new byte[9];
            int one = a*i, two = b*i, three = c*i;
            if (one > 100 && one < 1000 && two > 100 && two < 1000 && three > 100 && three < 1000
                    && judge(one) && judge(two) && judge(three)) {
                flag = true;
                System.out.println(one + " " + two + " " + three);
            }
        }
        if (!flag) {
            System.out.println("No!!!");
        }
    }

}
按比例切分组合数值(洛谷P1008、P1618题解,Java语言描述)按比例切分组合数值(洛谷P1008、P1618题解,Java语言描述) 进阶的JFarmer 发布了364 篇原创文章 · 获赞 623 · 访问量 4万+ 私信 关注
上一篇:open-falcon架构详解


下一篇:spring log4j.properties 没有日志的问题