Java 盾神与砝码称重

电玩女神 2022-04-23 01:30 178阅读 0赞

问题描述  
　　有一天，他在宿舍里无意中发现了一个天平！这个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品去称。神奇的是，盾神一早就知道这m种物品的重量，他现在是想看看这个天平能不能称出这些物品出来。但是盾神稍微想了1秒钟以后就觉得这个问题太无聊了，于是就丢给了你。  
输入格式  
　　第一行为两个数，n和m。  
　　第二行为n个数，表示这n个砝码的重量。  
　　第三行为m个数，表示这m个物品的重量。  
输出格式  
　　输出m行，对于第i行，如果第i个物品能被称出，输出YES否则输出NO。  
样例输入  
4 2  
1 2 4 8  
15 16  
样例输出  
YES  
NO  
样例输入  
4 1  
10 7 1 19  
1 7 10 19  
6  
样例输出  
YES  
数据规模和约定  
　　1<=n<=24, 1<=m<=10.

> 这是我的思路：砝码可以加在左称也可以加在右称所以要着重注意。  
> 我写的jia方法就是一味的给左称加砝码，加到与物体重量一致。首先把砝码质量排序，从最大的开始比较，物体还需比较的质量大于砝码质量才行，当最小的砝码都使用了，还需比较的质量不为0，表示失败；为0成功。  
> 我写的jian方法就是算砝码也可以加在右称的情况。判断物体质量与最大砝码的质量差，然后判断剩余砝码能否填满这个质量差，类似jia方法，当最小的砝码用完了还不相等。舍弃当前最大砝码，把下一个最大砝码当成最大砝码重复上述思路。最小砝码都比过了还是无法匹配，直接失败。  
> 代码：

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Test {
        public static boolean jia(int arr[], int x, int n, int m) {
                for (int j = n - 1; j >= 0; j--) {
                    if (x >= arr[j]) {
                        x = x - arr[j];
                    }
                }
            for (int i = 0; i < m; i++) {
                if (x == 0) {
                    return true;
                }
            }
            return false;
        }
    
        public static boolean jian(int arr[], int x, int n, int m) {
            if (arr[n - 1] < x) {
                return false;
            }
            int count = 1;
            for (int i = 0; i < n; i++) {
                int tmp = arr[n - count] - x;
                for (int j = n - 1 - count; j >= 0; j--) {
                    if (tmp >= arr[j]) {
                        if (tmp == arr[j]){
                            return true;
                        }
                        tmp = tmp - arr[j];
                    }
                }
                count++;
            }
            for (int i = 0; i < m; i++) {
                if (x == 0) {
                    return true;
                }
            }
            return false;
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] arr = new int[n];
            int[] brr = new int[m];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            for (int i = 0; i < m; i++) {
                brr[i] = sc.nextInt();
            }
            Arrays.sort(arr);
            for (int i = 0; i < m; i++) {
                if (jia(arr, brr[i], n, m)) {
                    System.out.println("YES");
                } else if (jian(arr, brr[i], n, m)) {
                    System.out.println("YES");
                } else {
                    System.out.println("No");
                }
            }
        }
    }