稻谷粒

用户名：uq_78133080422

访问量：3495

签　名：

等　　级
排　　名	2691
经　　验	2191
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯基础练习VIP-Huffuman树
浏览：694

蓝桥杯算法提高VIP-盾神与积木游戏
浏览：156

卢卡斯定理 & 快速幂算法 & 二项式定理解公式求值问题（Java代码）
浏览：2010

你可能喜欢

蓝桥杯算法提高VIP-盾神与积木游戏

　　作者: 稻谷粒　　　　发表时间：2021-03-20 11:21:47 浏览：156　|　评论：0　

原题链接：蓝桥杯算法提高VIP-盾神与积木游戏

#  按需求的积木数升序排列，每一步先满足最小需求的小朋友

## 解题思路

很明显用贪心思想来看就知道解决此题的其中一条思路就是：**每一步先满足需求最小的小朋友**，然后将他的积木贡献出来成为“公共积木”，以此循环。如果执行到某一步：**现能提供的最大数量的积木连最小的需求也无法满足，直接打印NO**

成功结束循环就打印**YES**

**具体实现可以看代码，有较多注释**

> **注意**

**对二维数组的按指定列排序有很多方法，这里我采用直接重写Arrays.sort方法中的比较器参数：`Comparator`来实现。**

## 代码实现

```java
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[][] arr = new int[n][2];// 每行代表一个小朋友：[现有的积木数][需要的积木数]
			// 找出已经完成作品的小朋友，将他们的积木贡献出来
			int woodNum = 0;
			int count = 0;// 已经完成作品的小朋友数
			for (int i = 0; i < n; i++) {
				arr[i][0] = scanner.nextInt();
				arr[i][1] = scanner.nextInt();
				if (arr[i][0] >= arr[i][1]) {
					woodNum += arr[i][0];
					count++;
					Arrays.fill(arr[i], 0);// 此时该小朋友所需积木为0，所有的积木也就置为0
				}
			}
			// 贪心：按需求的积木数升序排列，每一步先满足最小需求的小朋友
			sort(arr);
			for (int i = count; i < n; i++) {
				if ((arr[i][0] + woodNum) < arr[i][1]) {// 现能提供的最大数量的积木连最小的需求也无法满足，直接打印NO
					System.out.println("NO");
					break;
				} else {
					woodNum += arr[i][0];// 可提供的积木数更新
					Arrays.fill(arr[i], 0);
				}
			}
			if (arr[n - 1][1] == 0) {// 最后一个小朋友也完成了作品
				System.out.println("YES");
			}
			m--;
		}
		scanner.close();
	}
	// 二维数组按1号元素升序排序
	public static void sort(int[][] arr) {
		// 重写compare函数实现对二维数组指定列进行升序排序
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[1] - b[1];
			}
		});
	}
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

稻谷粒

TA的其他文章

你可能喜欢

DNA （C++代码）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

简单的a+b （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-盾神与积木游戏

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1014题解

有关字符，字符串的输入输出函数说明

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

蛇行矩阵（C语言代码）

整除的尾数（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

稻谷粒

TA的其他文章

你可能喜欢

DNA （C++代码）

C语言训练-尼科彻斯定理 （C语言代码）。。。内含证明定理

简单的a+b （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

蓝桥杯算法提高VIP-盾神与积木游戏

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1014题解

有关字符，字符串的输入输出函数说明

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

蛇行矩阵 （C语言代码）

整除的尾数 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

【亲和数】（C语言代码）

　　评论区

蛇行矩阵（C语言代码）

整除的尾数（C语言代码）

C二级辅导-分段函数（C语言代码）