首页 > 试题广场 >

小熊吃糖

[编程题]小熊吃糖

热度指数：6370 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有n只小熊，他们有着各不相同的战斗力。每次他们吃糖时，会按照战斗力来排，战斗力高的小熊拥有优先选择权。前面的小熊吃饱了，后面的小熊才能吃。每只小熊有一个饥饿值，每次进食的时候，小熊们会选择最大的能填饱自己当前饥饿值的那颗糖来吃，可能吃完没饱会重复上述过程，但不会选择吃撑。

现在给出n只小熊的战斗力和饥饿值，并且给出m颗糖能填饱的饥饿值。

求所有小熊进食完之后，每只小熊剩余的饥饿值。

输入描述:

第一行两个正整数n和m，分别表示小熊数量和糖的数量。（n <= 10, m <= 100）
第二行m个正整数，每个表示着颗糖能填充的饥饿值。
接下来的n行，每行2个正整数，分别代表每只小熊的战斗力和当前饥饿值。
题目中所有输入的数值小于等于100。

输出描述:

输出n行，每行一个整数，代表每只小熊剩余的饥饿值。

示例1

输入

2 5
5 6 10 20 30
4 34
3 35

输出

4
0

说明

第一只小熊吃了第5颗糖
第二只小熊吃了第4颗糖
第二只小熊吃了第3颗糖
第二只小熊吃了第1颗糖

算法知识视频讲解

Java

牛客393231125号

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        List<Integer> food = new LinkedList<>();
        int n = in.nextInt(), m = in.nextInt();
        for(int x = 0; x < m; x++) food.add(in.nextInt());
        Comparator<int[]> comparator = (a, b) -> b[0] - a[0];
        PriorityQueue<int[]> queue = new PriorityQueue<>(comparator);
        for(int x = 0; x < n; x++){
            int[] num = new int[3];
            num[0] = in.nextInt();
            num[1] = in.nextInt();
            num[2] = x;
            queue.offer(num);
        }


        Collections.sort(food);
        int[] ans = new int[n];
        for(int[] x : queue){
            for(int y = food.size() - 1; y >= 0; y--){
                if(x[1] - food.get(y) >= 0){
                    x[1] -= food.get(y);
                    food.remove(y);
                }
                if(x[1] == 0) break;
            }
            ans[x[2]] = x[1];
        }
        for(int x: ans) System.out.println(x);


    }
}

兄弟们这为什么不对

发表于 2025-04-09 15:53:55 回复(0)

Java

BruceLee_烽火

import java.util.*;

import static java.util.Arrays.sort;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[m];
        Map<Integer,Integer> map = new TreeMap<>(Comparator.reverseOrder());
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
        }
        sort(a);
        for (int i = 0; i < n; i++) {
            map.put(sc.nextInt(), sc.nextInt());
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> en: entries) {
            int value = en.getValue();
            for (int i = m-1; i >=0 ; i--) {
                if(value>=a[i] && a[i]!=0){
                    value-=a[i];
                    a[i] = 0;
                }
            }
            System.out.println(value);
        }
    }
}

有大佬解释下我的问题么

发表于 2024-07-21 21:31:52 回复(0)

Java

再向前一点

1. 使用Map<战斗力，下标>记录熊原来位置（题中没有说明战斗力相同的情况，那么假设每个熊战斗力都不同，map的key即为熊的唯一ID）

2. 糖果和熊都进行排序

3. 遍历熊，遍历糖果，贪心选择

import java.util.Scanner;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] candy = new int[m];
        for(int i=0;i<m;i++)
            candy[i]=in.nextInt();
        int[][] bears = new int[n][2];
        Map<Integer,Integer> mapPos = new HashMap<>();
        for(int i=0;i<n;i++){
            bears[i][0] = in.nextInt();
            bears[i][1] = in.nextInt();
            mapPos.put(bears[i][0],i);
        }
        Arrays.sort(candy);
        Arrays.sort(bears,(n1,n2)->n1[0]-n2[0]);
        int[] res = new int[n];
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(bears[i][1]>=candy[j]){
                    bears[i][1]-=candy[j];
                    candy[j]=0;
                }
            }
            res[mapPos.get(bears[i][0])] = bears[i][1];
        }
        for(int i=0;i<n;i++){
            System.out.println(res[i]);
        }
    }
}

发表于 2021-08-24 10:45:22 回复(1)

Java

Mono_Chrome

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    //熊类
    public static class Bear {
        int attack; //战斗力
        int hungry; //饥饿值

        public Bear(int attack, int hungry) {
            this.attack = attack;
            this.hungry = hungry;
        }
    }

    //比较器，按战斗力逆序排行
    public static class descComparator implements Comparator<Bear> {
        public int compare(Bear p1, Bear p2) {
            return p1.attack != p2.attack ? p2.attack - p1.attack : p1.hungry - p2.hungry;
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Bear[] pandas = new Bear[n];
        int[] sugar = new int[m];
        for (int i = 0; i < m; i++) {
            sugar[i] = sc.nextInt();
        }
        //用哈希表保证最终结果能够不被排序打乱
        HashMap<Integer, Bear> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int attack = sc.nextInt();
            int hungry = sc.nextInt();
            pandas[i] = new Bear(attack, hungry);
            map.put(i, pandas[i]);
        }

        //按战斗力排序熊类数组
        Arrays.sort(pandas, new descComparator());
        //按糖给的能量排序糖类数组
        Arrays.sort(sugar);

        for (int i = 0; i < n; i++) {
            for (int j = m - 1; j >= 0; j--) {
                if (sugar[j] != -1 && pandas[i].hungry - sugar[j] >= 0) {
                    pandas[i].hungry -= sugar[j];
                    sugar[j] = -1; //吃完糖将其置为-1
                }
            }
        }
        //打印结果
        for (int i = 0; i < n; i++) {
            System.out.println(map.get(i).hungry);
        }
    }

}

发表于 2019-06-12 14:47:54 回复(0)