MENU

盾神与积木游戏

• December 23, 2020 • Read: 22 • 贪心

原题链接

问题描述

最近的m天盾神都去幼儿园陪小朋友们玩去了~
每个小朋友都拿到了一些积木,他们各自需要不同数量的积木来拼一些他们想要的东西。但是有的小朋友拿得多,有的小朋友拿得少,有些小朋友需要拿到其他小朋友的积木才能完成他的大作。如果某个小朋友完成了他的作品,那么他就会把自己的作品推倒,而无私地把他的所有积木都奉献出来;但是,如果他还没有完成 自己的作品,他是不会把积木让出去的哟~
盾神看到这么和谐的小朋友们感到非常开心,于是想帮助他们所有人都完成他们各自的作品。盾神现在在想,这个理想有没有可能实现呢?于是把这个问题交给了他最信赖的你。

数据规模和约定
1<=n<=10000,1<=m<=10。

输入

第一行为一个数m。
接下来有m组数据。每一组的第一行为n,表示这天有n个小朋友。接下来的n行每行两个数,分别表示他现在拥有的积木数和他一共需要的积木数。

输出

输出m行,如果第i天能顺利完成所有作品,输出YES,否则输出NO。


解法

Idea :

(1)要尽可能的拼凑出来,有两个方向:第一,先拼出积木数多的,再释放出来以拼所需数目少的;第二,先拼出所需积木数少的,再释放出来以拼所需数目多的。如果走方式一,当可用的积木少于所需积木,直接就拼不了,因此方式一欠妥。如果采用方式二,先用已有积木往所需数目少的那里凑,拼好了再释放,到最后去拼凑所需积木大的,这样才尽可能拼出来
(2)用二维数组nums[][3],存储数据。Nums[][0]表示已有积木,nums[][1]表示拼出该物积木总数,nums[][2]表示现在还需要多少个积木。
(3)计算出不经调整就能拼好(即nums[][2] <= 0),释放的积木数量
(4)对所需积木数量进行从小到大排序
(5)用已有的积木数量补齐缺少的积木数量,如果能拼好,则释放,如果不能拼好,则今天这个不能调整成功,输出“NO”

代码

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        while (m != 0){
            int n = scanner.nextInt();
            int[][] nums = new int[n][3];
            for (int i = 0; i < n; i++) {
                nums[i][0] = scanner.nextInt();
                nums[i][1] = scanner.nextInt();
                nums[i][2] = nums[i][1] - nums[i][0];
            }
            int current = 0;
            Arrays.sort(nums, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[2] - o2[2];
                }
            });
            // 已经堆积好了的小朋友
            for (int i = 0; i < n; i++) {
                if(nums[i][2] <= 0){
                    current += nums[i][0];
                }
            }
            // 没有堆积好的朋友
            for (int i = 0; i < n; i++) {
                if(nums[i][2] > 0){
                    // 填补
                    current -= nums[i][2];
                    if(current < 0){
                        System.out.println("NO");
                        break;
                    }else {
                        current += nums[i][1];
                    }
                }
            }
            if(current >= 0){
                System.out.println("YES");
            }
            -- m;
        }
    }

}

提交结果




作者:喻航

本文标题:盾神与积木游戏

本文链接:https://onedawn.cn/greed/153.html

版权声明:如无特别声明,本文即为原创文章,仅代表个人观点,版权归 雾满拦江 所有,未经允许不得转载!
Archives Tip
QR Code for this page
Tipping QR Code