题目描述

六一儿童节,老师带了很多好吃的巧克力到幼儿园。每块巧克力j的重量为w[j],对于每个
小朋友i,当他分到的巧克力大小达到h[i] (即w[j]>=h[i]),他才会上去表演节目。老师
的目标是将巧克力分发给孩子们,使得最多的小孩上台表演。可以保证每个w[i]> 0且不能
将多块巧克力分给一个孩子或将一块分给多个孩子。
输入描述:
第一行:n,表示h数组元素个数
第二行:n个h数组元素
第三行:m,表示w数组元素个数
第四行:m个w数组元素
输出描述:
上台表演学生人数
示例1
输入
3
2 2 3
2
3 1
输出
1

题目分析

首先由题目的意思可以理解为,有m块特定重量的巧克力,
分给h个人,如果那个人得到的巧克力重量大于期望的,就会去上台表演。
那么怎么分配这些巧克力使上台的人数最大。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。


思路分析

由贪心算法的思想,尽可能的使得每让一个人上台,花费最小重量
巧克力,这样剩下的巧克力就能够分给更多的人。

那么怎么实现呢?将巧克力的重量数组,按照从小到大排序,依次选出最小重量的
巧克力,换句话说,每次都只使用最小重量的巧克力,那么剩下的一定是最多的,遍历h数组,看看是否可以使得孩子上台,如果可以计数器加1。

import java.util.Arrays; import java.util.Scanner; public class ChildernDay { public static void main(String args[]) { Scanner scn = new Scanner(System.in); // 计数器,上台的人数
      int num=0; // 输入小孩的人数h
      int h = scn.nextInt(); int[] child = new int[h]; // 循环输入期望分到的巧克力重量
      for(int i=0;i<h;i++) { child[i] = scn.nextInt(); } // 输入巧克力的个数
      int m = scn.nextInt(); int[] weight = new int[m]; for(int i=0;i<m;i++) { weight[i]=scn.nextInt(); } // 使用选择排序方法-----可以使用java中的Arrays.sort // for(int i=0;i<m;i++) { // int value = i; // for(int j=i+1;j<m;j++) { // if(weight[j]<weight[value]) { // value = j; // } // } // if(value != i) { // int temp = weight[i]; // weight[i] = weight[value]; // weight[value] = temp; // } // } // 可以使用快速排序,提升排序的速度
 Arrays.sort(weight); // 依次选出巧克力数组中重量最小的巧克力
      for(int i=0;i<m;i++) {
// 遍历孩子数组
for(int j=0;j<h;j++) {
// 这里注意,当孩子已经上台,就跳过。
if(child[j]==-1) continue; if(weight[i]>=child[j]) { num++; child[j] = -1; break; } } }

// 优化方案---事先对孩子数组进行排序,同时j变量的定义也可以发现,也使用了贪心的思想,

// 如果巧克力的重量连孩子中期望的最小重量都不满足的话,其他的肯定也不满足。
// Arrays.sort(child);
// int i=0;
// int j=0;
// while(i<m && j<h) {
//     if(weight[i]<child[j]) {
//         i++;
//     }
//     else {
//         num++;
//         i++;
//         j++;
//     }
// }

 System.out.println(num); } }

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄