首页 > 试题广场 >

小熊吃糖

[编程题]小熊吃糖

热度指数：5969 时间限制：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

再向前一点

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 回复(0)

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)