首页 > 试题广场 >

餐馆

[编程题]餐馆
  • 热度指数：25420 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
某餐馆有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
算法知识视频讲解
开通博客
头像 哈哈哈哈鹅
发表于 2022-04-26 15:48:02
对于这个题目，要求总预计消费金额最大，那么就是每一批客人的预计消费金额都要尽可能的大，那么就体现了贪心的思想，每一次都取最大的 就可以对客人的预计消费金额进行降序排序，安排完了最大的客人，接下来就是次大的，这样就可以保证总消费金额是最大的 还有一个思想就是二分法的思想，首先我们可以对桌子的容 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 卷起来卷起来
发表于 2021-05-02 23:23:19
//按餐桌可容纳人数 升序排列 nArr.sort((a, b) => { return a - b; }); //按每批客人的 预计消费金额 升序排列 mArr.sort((a, b) => { return -(a.c - b.c); }); function fun(n, 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客591847084号
发表于 2022-02-06 20:11:58
使用的贪心策略，优先将消费最大，占用座位较少的消费者排号就座。 #include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 滴滴 排序 贪心 Java工程师
上传者：小小
难度：
87条回答 21544浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号