对于这个题目，要求总预计消费金额最大，那么就是每一批客人的预计消费金额都要尽可能的大，那么就体现了贪心的思想，每一次都取最大的 就可以对客人的预计消费金额进行降序排序，安排完了最大的客人，接下来就是次大的，这样就可以保证总消费金额是最大的
还有一个思想就是二分法的思想，首先我们可以对桌子的容纳人数进行升序排序，然后定义一个是否安排座位的数组保证不重复查找，这样在遍历每一批客人，
也就是客人进行安排座位的时候就可以
根据每一批客人的人数进行安排座位，如果客人的人数大于桌子容纳人数的最大值，那么就直接跳过这一批客人，如果客人的人数小于等于桌子的容纳人数
那么就要进行查找桌子的座位了，如果客人的人数小于等于桌子数组中间下标的值，那么就不会往后面去安排座位，直接从桌子数组的中间下标以前去找座位
如果客人的人数大于桌子数组中间下标的值，那么就不会往前面去安排座位，就往中间下标以后去找座位，当然在找座位的过程中，
需要看这个座位是不是已经超过了桌子数组的下标，还需要看这个桌子是不是已经被安排了，如果座位下标合法，座位没有被安排，那么就可以累加最大值
如果座位合法，但是座位被安排了，那么就直接在桌子数组里找下一个位置，直到找到一个没有被安排的桌子为止
在这个查找期间还可以做一个优化就是引入桌子的计数情况，如果客人被安排的桌子数等于了桌子数组的个数，那么就退出循环，不用再找了，直接返回最大值即可
对于这个题目有两种做法：
①：用数组存储n个桌子，对数组升序排序，用数组存储m批客人，对客人的消费金额利用Comparator接口的compare方法进行降序排序
如果客人的人数超过桌子的最大容纳人数，那么直接跳过这个循环，安排下一批客人，
定义被安排座位的数组防止被重复访问，定义一个桌子计数器，节省时间，只要客人被安排的桌子数等于了桌子数组的个数那么就退出安排座位的循环
遍历每一批客人，使用一个二分法给客人安排座位，只要这个座位合法没有被安排，那么就计入最大值，并且把这个桌子记为安排过了
如果座位合法但是被安排了，那么就在桌子数组里找下一个桌子，如果计数器达到了n.那么就退出循环，返回最大值
②：用数组存储n个桌子，对数组升序排序，使用堆存储客人类，继承comparable接口，在这个类里存储了客人的人数和客人的预计消费金额
使用compareTo方法对客人的预计消费金额进行降序排序，
在输入m批客人的时候，我们只将客人的人数小于等于桌子数组最大容纳人数的客人类加入堆，因为超过最大容纳人数的客人安排不了座位
这样既优化了时间复杂度也实现了降序排序。
定义一个被安排的数组，长度是n,防止桌子被重复安排，定义一个计数器，只要客人被安排一批，最大值就累加一次的同时计数器就+1
然后就遍历桌子数组开始分配座位，依次弹出堆元素，如果堆元素的人数属性小于等于桌子容纳人数并且这个桌子没有被安排，那么就计入最大值
桌子计数器+1，设置这个桌子为安排过，退出循环，看被安排的桌子数是否等于桌子数组的个数，接着再遍历下一批客人，也就是继续退出堆元素
重复以上判断步骤，直到计数器累加为n，返回最大金额。
import java.util.*;
public class Main{
public static void main(String[] args) {
// 法一：
// Scanner scan=new Scanner(System.in);
// while (scan.hasNext()) {
// //n表示桌子数，a表示每桌容纳的最多人数，m表示客人的批数，b表示每批客人的人数，c表示每批客人的预计消费金额
// //第一行输入n和m
// int n = scan.nextInt();
// int m = scan.nextInt();
// //输入每桌容纳的最大人数，用数组保存
// int[] disks = new int[n];
// for (int i = 0; i < n; i++) {
// disks[i] = scan.nextInt();
// }
// //将桌子容纳人数从小到大排序
// Arrays.sort(disks);
// int[][] bc=new int[m][2];
// for(int i=0;i<m;i++){
// bc[i][0]=scan.nextInt();
// bc[i][1]=scan.nextInt();
// }
// //对客人数组的预计消费金额按照降序排序
// Arrays.sort(bc,new Comparator<int[]>(){
// @Override
// public int compare(int[] o1,int[] o2) { //客人数组的列也是一维数组
// return o2[1]-o1[1]; //只对客人数组列进行降序排序，
// }
// });
// //定义被安排数组,也就是看桌子是不是被占用
// boolean[] visited=new boolean[n];
// long maxMoney=0L;
// int count=0; //对客人安排的桌子进行计数
// //遍历m批客人，也就是所说的安排座位
// for(int i=0;i<m;i++){
// //如果一批客人的人数大于桌子容纳人数的最大值，那么就直接跳过，安排下一批客人
// if(bc[i][0]>disks[n-1]){
// continue;
// }
// //拿到每一批客人的人数和消费金额
// int b=bc[i][0];
// int c=bc[i][1];
// //如果桌子能够容纳客人的个数，那么就安排座位
// //这里可以根据客人的人数和桌子的容纳人数进行二分查找座位，返回的是桌子数组的下标
// int index=binarySearch(b,disks);
// //找到了一个桌子就需要看这个桌子的下标是不是合法的，并且这个桌子有没有被安排过
// while (index<n && visited[index]){
// //被安排过了就找下一个桌子
// index++;
// }
// //这个桌子合法，而且没有被安排，那么就累计最大值，标记为安排过
// if(index < n){
// maxMoney+=c;
// visited[index] = true;
// count++;
// if(count==n){
// break;
// }
// }
// }
// System.out.println(maxMoney);
// }
// }
// public static int binarySearch(int b,int[] disks){
// //二分查找座位，如果客人的人数小于等于桌子中间下标的容纳人数，那么这批客人的座位就从桌子数组中间下标的前面找，反之就从中间下标后面找
// //直到左边下标大于右边的下标，那么就找到了，返回左边下标
// int left=0;
// int right=disks.length-1;
// while(left<=right){
// int mid=(left+right)/2;
// if(b>disks[mid]){
// left=mid+1;
// }else{
// right=mid-1;//如果是right=mid就会造成死循环，导致时间复杂度过大，也就是当left,rigth,mid在一起时，如果条件一直成立，那么就会造死循环
// }
// }
// return left;
// }
//法二：
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
//输入桌子数和客人批数
int n=scan.nextInt();
int m=scan.nextInt();
int[] disks=new int[n];
for(int i=0;i<n;i++){
disks[i] = scan.nextInt();
}
Arrays.sort(disks);
//定义一个被安排的数组，防止重复安排
boolean[] visited=new boolean[n];
int count=0; //对安排的桌子个数进行计数
long max=0L;
//输入每一批客人，在输入的时候，把每一批客人人数小于等于桌子容纳最大值的客人对象入堆，
// 客人对象实现了Comparable接口的compareTo方法，对客人对象的预计消费金额进行排序
PriorityQueue<Customer> priorityQue=new PriorityQueue<>();
for(int i=0;i<m;i++){
int people=scan.nextInt();
int price=scan.nextInt();
//优先级队列里只存储桌子能容纳的i批客人
if(people<=disks[n-1]){
priorityQue.add(new Customer(people,price));
}
}
//给客人分配桌子
while(!priorityQue.isEmpty()){
//弹出堆里的客人对象
Customer cur=priorityQue.poll();
//遍历每个桌子
for(int i=0;i<n;i++){
//如果客人的人数小于桌子的容纳人数，并且没有被访问过，那么就计数，并把桌子标记为已经安排过
if(cur.people<=disks[i] && !visited[i]){
max+=cur.price;
count++;
visited[i] = true;
break; //安排了一批客人就安排下一批客人
}
}
if(count==n){
break; //如果桌子被安排完了，那么其他的客人就不同再从堆里弹出了，已经没有机会了
}
}
System.out.println(max);
}
} static class Customer implements Comparable<Customer>{
private final int people;
private final int price;
public Customer(int people, int price) {
this.people = people;
this.price = price;
}
@Override
public int compareTo(Customer o) {
return o.price-this.price;
}
}
}
京公网安备 11010502036488号