题解 | #餐馆#
餐馆
https://www.nowcoder.com/practice/d2cced737eb54a3aa550f53bb3cc19d0
解题思路
这是一道餐馆安排座位的贪心题目，主要思路如下：
-
问题分析：
张桌子，每张桌子有容纳上限
批客人，每批客人有人数和消费金额
- 不允许拼桌
- 求最大总收入
-
解决方案：
- 按照消费金额从大到小排序客人
- 对每批客人，找到能容纳且最小的桌子
- 使用
multiset维护桌子容量，方便查找和删除
-
贪心策略：
- 优先安排消费高的客人
- 为每批客人分配能容纳的最小桌子
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
// 客人结构体
struct Guest {
int num; // 人数
int money; // 消费金额
};
// 按消费金额降序排序
bool cmp(Guest a, Guest b) {
if(a.money == b.money) return a.num < b.num;
return a.money > b.money;
}
int main() {
int n, m;
while(cin >> n >> m) {
// 读入桌子容量
multiset<int> tables;
for(int i = 0; i < n; i++) {
int capacity;
cin >> capacity;
tables.insert(capacity);
}
// 读入客人信息
vector<Guest> guests(m);
for(int i = 0; i < m; i++) {
cin >> guests[i].num >> guests[i].money;
}
// 按消费金额排序
sort(guests.begin(), guests.end(), cmp);
// 安排座位
long long total = 0;
for(int i = 0; i < m; i++) {
if(tables.empty()) break;
// 找到能容纳的最小桌子
auto it = tables.lower_bound(guests[i].num);
if(it != tables.end()) {
total += guests[i].money;
tables.erase(it);
}
}
cout << total << endl;
}
return 0;
}
import java.util.*;
public class Main {
// 客人类
static class Guest {
int num, money;
Guest(int num, int money) {
this.num = num;
this.money = money;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
// 读入桌子容量
TreeMap<Integer, Integer> tables = new TreeMap<>();
for(int i = 0; i < n; i++) {
int capacity = sc.nextInt();
tables.put(capacity, tables.getOrDefault(capacity, 0) + 1);
}
// 读入客人信息
Guest[] guests = new Guest[m];
for(int i = 0; i < m; i++) {
guests[i] = new Guest(sc.nextInt(), sc.nextInt());
}
// 按消费金额排序
Arrays.sort(guests, (a, b) -> {
if(a.money != b.money) return b.money - a.money;
return a.num - b.num;
});
// 安排座位
long total = 0;
for(Guest g : guests) {
Map.Entry<Integer, Integer> entry = tables.ceilingEntry(g.num);
if(entry != null) {
total += g.money;
if(entry.getValue() == 1) {
tables.remove(entry.getKey());
} else {
tables.put(entry.getKey(), entry.getValue() - 1);
}
}
}
System.out.println(total);
}
}
}
from typing import List
import bisect
from collections import Counter
def max_revenue(n: int, m: int, tables: List[int], guests: List[List[int]]) -> int:
# 将桌子容量排序
tables.sort()
# 将客人按消费金额降序排序
guests.sort(key=lambda x: (-x[1], x[0]))
# 使用Counter来模拟multiset
table_count = Counter(tables)
available_tables = sorted(table_count.keys())
total = 0
for num, money in guests:
# 找到能容纳的最小桌子
idx = bisect.bisect_left(available_tables, num)
if idx < len(available_tables):
table_size = available_tables[idx]
total += money
table_count[table_size] -= 1
if table_count[table_size] == 0:
available_tables.pop(idx)
return total
def main():
while True:
try:
n, m = map(int, input().split())
tables = list(map(int, input().split()))
guests = []
for _ in range(m):
num, money = map(int, input().split())
guests.append([num, money])
print(max_revenue(n, m, tables, guests))
except EOFError:
break
if __name__ == "__main__":
main()
算法及复杂度
- 算法：贪心算法
- 时间复杂度：
- 排序和查找的复杂度
- 空间复杂度：
- 存储桌子和客人信息
