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

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