[编程题]餐馆
- 热度指数：26293 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
某餐馆有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
对于这个题目，要求总预计消费金额最大，那么就是每一批客人的预计消费金额都要尽可能的大，那么就体现了贪心的思想，每一次都取最大的
就可以对客人的预计消费金额进行降序排序，安排完了最大的客人，接下来就是次大的，这样就可以保证总消费金额是最大的
还有一个思想就是二分法的思想，首先我们可以对桌子的容
展开全文
import java.util.*;
public class Main {
static boolean[] used;
static long res;
public static void main(String[] args) {
Scanner
展开全文
使用的贪心策略，优先将消费最大，占用座位较少的消费者排号就座。
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace
展开全文
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
int
展开全文
import sys
from typing import List
inputs = []
for line in sys.stdin:
inputs.extend(map(int, line.split()))
def takeSecond(elem):
return ele
展开全文
//按餐桌可容纳人数 升序排列
nArr.sort((a, b) => {
return a - b;
});
//按每批客人的 预计消费金额 升序排列
mArr.sort((a, b) => {
return -(a.c - b.c);
});
function fun(n,
展开全文
解题思路
这是一道餐馆安排座位的贪心题目，主要思路如下：
问题分析：
张桌子，每张桌子有容纳上限
批客人，每批客人有人数和消费金额
不允许拼桌
求最大总收入
解决方案：
按照消费金额从大到小排序客人
对每批客人，找到能容纳且最小的桌子
使用 multiset 维护桌子容量，方便查找
展开全文
朴素做法，分别排序桌子和客人，再逐个安排
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
展开全文
二分，寻找每一次能匹配上的比较大的桌子，实际上这道题还能用最大堆做。
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[]
展开全文
问题信息
通过挑战的用户
查看代码-
2023-03-15 08:50:56
-
2022-11-07 12:02:05
-
2022-10-18 22:17:13
-
2022-10-15 17:55:35
-
2022-10-15 16:40:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
