Java 贪吃的大嘴

刺骨的言语ヽ痛彻心扉 2022-03-21 13:28 99阅读 0赞

## 问题描述 ##

有一只特别贪吃的大嘴,她很喜欢吃一种小蛋糕,而每一个小蛋糕有一个美味度,而大嘴是很傲娇的,一定要吃美味度和刚好为m的小蛋糕,而且大嘴还特别懒,她希望通过吃数量最少的小蛋糕达到这个目的.所以她希望你能设计一个程序帮她决定要吃哪些小蛋糕.  
输入格式  
　　先输入一行包含2个整数m、n,表示大嘴需要吃美味度和为m的小蛋糕,而小蛋糕一共有n种,下面输入n行,每行2个整数,第一个表示该种小蛋糕的美味度,第二个表示蛋糕店中该种小蛋糕的总数  
输出格式  
　　输出一行包含一个整数表示大嘴最少需要吃的小蛋糕数量,若大嘴无法通过吃小蛋糕达到m的美味度和,则输出"><“.  
样例输入  
10 2  
4 1  
2 10  
样例输出  
4  
样例输入  
10 2  
4 1  
7 3  
样例输出

> <  
> 数据规模和约定  
> 　　m ≤ 20000,小蛋糕总数量≤50.

## 代码： ##

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
                b[i] = scanner.nextInt();
            }
            int count = 0;
            for (int i = 0; i < n; i++) {
                count += b[i];
            }
            int[] c = new int[count];
            int tmp = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < b[i]; j++) {
                    c[tmp++] = a[i];
                }
            }
            Arrays.sort(c);
            int x = 0;
            for (int i = count-1; i >=0; i--) {
                if (m >= c[i]) {
                    m -= c[i];
                    x++;
                }
            }
            if (m!=0){
                System.out.println("><");
            }else {
                System.out.println(x);
            }
        }
    }