#yyds干货盘点# 名企真题专题:餐馆

时间:2022-12-21 11:18:33

1.简述:

描述

某餐馆有n张桌子,每张桌子有一个参数:a 可容纳的最大人数; 有m批客人,每批客人有两个参数:b人数,c预计消费金额。 在不允许拼桌的情况下,请实现一个算法选择其中一部分客人,使得总预计消费金额最大

输入描述:

输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行,每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。

输出描述:

输出一个整数,表示最大的总预计消费金额

示例1

输入:

3 5 2 4 2 1 3 3 5 3 7 5 9 1 10

输出:

20

2.代码实现:

import java.util.*;
public class Main{
public static void main(String[] args) {

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;
}
}
}