首页 > 试题广场 >

餐馆

[编程题]餐馆
  • 热度指数：25425 时间限制：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
算法知识视频讲解
添加回答
Python
沉静如渊头像 沉静如渊
"""思路：
   1.为获得最大消费金额，应该按照消费金额降序排序，方便遍历和计算
   2.桌子容纳人数升序排列，方便在遍历能容得下第i批客人的时候使用二分查找，这里二分查找使用   python的内置模块bisect
   3.除去客人人数大于桌子可容纳的最大数量的数据组
   4.对桌子可容纳数量list进行二分查找，从而为客人分配桌子
"""
import bisect
import sys
n,m=map(int,input().split())
tableCanHold=sorted(list(map(int,input().split())),reverse=False)  # 容纳人数升序排序
cusAndMoney=[]
tMax=max(tableCanHold)
for each in sys.stdin.readlines():
    each0=int(each.split()[0])
    each1=int(each.split()[1])
    if(each0<=tMax):  # 除去客人人数大于桌子可容纳的最大数量的数据组
        cusAndMoney.append([each0,each1])
cusAndMoney.sort(key=lambda x:x[1],reverse=True)
money=0
for peo,pri in cusAndMoney:
    if(len(tableCanHold)==0):
        break
    index=bisect.bisect_left(tableCanHold,peo) # 二分查找插入位置，用于下面的判断
    if(index!=len(tableCanHold)): # 当index==len(tableCanHold)说明客人数量peo大于桌子可容纳的数量
        money+=pri
        tableCanHold.pop(index)  # 除去已被使用的桌子
print(money)
发表于 2019-09-02 21:56:39 回复(0)
Python
冉龙宇头像 冉龙宇

贪心算法，关键在排序和二分查找。 

nm = list(map(int, input().strip().split()))
ali = list(map(int, input().strip().split()))
bcli = []
for i in range(nm[1]):
    bcli.append(list(map(int, input().strip().split())))


def somesort(bcli, start, end):  # 对数字中某几行排序
    if start >= end:
        return
    for i in range(start, end + 1):
        mini = start + i
        for j in range(start + i, end + 1):
            if bcli[j][0] < bcli[mini][0]:
                mini = j
        if mini != start + i:
            bcli[mini], bcli[start + i] = bcli[start + i], bcli[mini]


def twosort(bcli):  # 先按第二列排序，再对第二列相同的按第一列排序
    bcli.sort(key=lambda line: line[1], reverse=True)
    start = 0  # 开始指针
    end = 0  # 结束指针
    while end < len(bcli):
        if (end + 1 < len(bcli) and bcli[start][1] != bcli[end + 1][1]) or end == len(bcli) - 1:
            somesort(bcli, start, end)
            end += 1
            start = end
        else:
            end += 1


def find(ali, num):  # 查找并删除
    i = 0
    while i < len(ali):
        if ali[i] >= num:
            ali.pop(i)
            return True
        i += 1
    return False


def binarySearach(ali, num):  # 二分查找第一个大于等于num的数，并删除
    l = 0
    r = len(ali) - 1
    while l <= r:
        mid = (l + r) // 2
        if ali[mid] >= num:
            if mid - 1 >= 0:
                if ali[mid - 1] >= num:
                    r = mid - 1
                else:
                    r = mid
                    break
            else:
                r = mid
                break
        else:
            l = mid + 1
    if l<=r:
        ali.pop(r)
        return True
    else:
        return False


ali.sort()
bcli.sort(key=lambda k: k[0])
bcli.sort(key=lambda k: k[1], reverse=True)
# twosort(bcli)
mon = 0
for person in bcli:
    sign = binarySearach(ali, person[0])
    #sign = find(ali, person[0])
    if sign:
        mon += person[1]
    if len(ali) == 0:
        break
print(mon)

'''
3 6
2 4 2
1 3
3 5
3 7
1 10
5 9
4 9
'''
编辑于 2019-08-26 18:17:20 回复(0)
Python
麻瓜工程师头像 麻瓜工程师
终于看了大佬的回答写出一版AC的了，重点在于客户的排序，首先当然需要按照金额大小排序，在金额大小相等的时候呢？应该按照人均消费进行排序，由高而低，安排桌子的时候应该从小桌开始安排。但是桌子的排序并不重要，相对而言。 
import bisect
table_num,custumer = map(int,input().split())
table_capacity = list(sorted((map(int,input().split()))))
c_m = [list(map(int,input().split())) for i in range(custumer)]
c_m = sorted(c_m,key=lambda x:[x[1],x[1]/x[0]],reverse = True)
money = 0
for cus,price in c_m:
    if not table_capacity:
        break
    index = bisect.bisect_left(table_capacity,cus)
    if index == len(table_capacity):
        continue
    else:
        money += price
        table_capacity.pop(index)
print(money)

唉，复杂度过大
通常的思路是对桌子按大小排序，对客人按消费金额排序，依次对比，如果桌子可以，就服务收费，如果不能，就跳过看下一位客人。 
table_num,custumer = map(int,input().split())
table_capacity = list(sorted((map(int,input().split())),reverse = True))
c_m = []
for i in range(custumer):
    c_m.append(list(map(int,input().split())))
c_m = sorted(c_m,key = lambda x:[x[1],x[0]],reverse = True)
money = 0
while table_capacity and c_m:
    chosen = c_m[0]
    c_m = c_m[1:]
    if table_capacity[0] < chosen[0]:
        continue
    differ = float('inf')
    for each in table_capacity:
        if 0 <= each - chosen[0] < differ:
            differ = each - chosen[0]
            ind = table_capacity.index(each)
    table_capacity.pop(ind)
    money += chosen[1]
print(money)
编辑于 2018-07-09 00:14:39 回复(0)
Python
yzdeng头像 yzdeng 
n,m=[int(x) for x in input().split()] #在m批客人中选择n批上n个桌子
table=[int(x) for x in input().split()] #每个桌子可容纳的最大人数
cus=[[int(x) for x in input().split()] for i in range(m)] #分别表示第i批客人的人数和预计消费金额

table.sort()#将桌子按可容纳人数从小到大排列
cus=sorted(cus,key=lambda x:x[0])#按每批顾客的人数进行从小到大排序
money=0#总金额

for i in range(n):
    temp=[]#盛放第i个桌子可接受的顾客批j
    for j in range(len(cus)): #注意range中要用cus的length时时更新
        if cus[j][0]>table[i]:
            break
        temp.append(cus[j])
    temp=sorted(temp,key=lambda x: x[1])#按消费金额排序
    if temp:
        money+=temp[-1][1]
        cus.remove(temp[-1])#此批客人已就坐

print(money)

发表于 2018-05-24 16:45:24 回复(3)
Python
新鲜菜鸡🐔头像 新鲜菜鸡🐔

暴力可以解决一切！！！

```
import functools
import bisect
def cmp(a,b):
    if a[1]>b[1]:
        return -1
    if a[1]==b[1] and a[0]<b[0]:
        return -1
    else:
        return 1
n,m = map(int,input().split())
zuozi = [int(x) for x in input().split()]
keren = [[int(x) for x in input().split()] for i in range(m)]
keren = sorted(keren,key=functools.cmp_to_key(cmp))
zuozi.sort()
ans = 0
for ren,jia in keren:
    if len(zuozi) ==0:
        break
    index = bisect.bisect_left(zuozi,ren)
    if index==len(zuozi):
        continue
    else:
        ans+=jia
        zuozi.pop(index)
print(ans)

```

发表于 2018-05-23 14:34:01 回复(2)
Python
庄绿洲头像 庄绿洲
贪心算法，从最有钱的食客开始招待，直到桌子坐满或者食客队列已空。难点是如何降低时间复杂度。比较好理解的是食客一个 for 循环餐桌一个 for 循环，时间复杂度 O(m*n) ，超时。于是我把餐桌循环改为用 binary search 来为每组食客找适合大小的桌子，时间复杂度降为 O(m*log(n))，测试通过。

PS：代码加了注释，在评论窗口这里一提交格式就乱，换行都丢失，根本就无法看了……你们 get 到点就好，python代码加起来也就四五十行的样子😂
编辑于 2017-11-09 01:54:12 回复(0)
Python
小欣8头像 小欣8 
if __name__ == '__main__':
    n, m = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    token = []
    for _ in range(m):
        token.append([int(x) for x in input().split()])
    a.sort()
    # 安装给钱多少排序
    token.sort(key=lambda x: x[1], reverse=True)
    b = [x[0] for x in token]
    c = [x[1] for x in token]
    ans = 0
    i = 0  # 给第i有钱客人安排桌子
    while a and i < m:  # 如果还有桌子还有客人
        # 二分搜索，给客人找桌子
        target = b[i]
        begin = 0
        end = len(a) - 1
        while begin < end:
            mid = (begin + end) >> 1
            if a[mid] < target:
                begin = mid + 1
            else:
                end = mid
        if a[begin] >= target:  # 如果有合适的桌子
            ans += c[i]
            a.pop(begin)
        i += 1
    print(ans)
编辑于 2017-09-27 11:17:38 回复(0)
Python
ITONGWORLD头像 ITONGWORLD

为什么用Python的heapq或Queue.PriorityQueue就会出现超时？
但关键是和Java的优先队列运行时间相比，就很困惑了。下图。
图片说明

发表于 2017-08-26 14:42:36 回复(0)
Python
什么时候才能成为红名大佬头像 什么时候才能成为红名大佬 
参考了大佬们二分法的思想，我自己直接贪心算法弄通过40%就超时了T_T
总之，自己水平太渣，有好多小细节没想到，加油加油，继续努力！
import sys
#大佬的二分法，用于选出可以容纳该批次人数的桌子（略大于人数的桌子，修改了终止条件和
# 相等的情况——（原谅我是小白，，，没啥高水平的解释））
def binarySearach(target, array):
    if target <= array[0]:
        return 0
    if target > array[-1]:
        return -1
    lo, hi = 0, len(array) - 1
    while lo+1 != hi:
        mid = (lo+hi)>>1
        if target <= array[mid]:
            hi=mid
        else:
            lo=mid
    return hi

n,m= map(int,sys.stdin.readline().strip().split())
num = map(int, sys.stdin.readline().strip().split())
man=[]
money=[]
for i in range(m):
    b,c = map(int, sys.stdin.readline().strip().split())
    man.append(b)
    money.append(c)
num.sort()

sum_ = 0
cnt =0
# 按盈利降序排列
order = sorted(range(m),key=lambda k:money[k],reverse = True)
for i in order:
    idx=binarySearach(man[i],num)
    if idx>=0:  #若是-1，说明比num中最大的桌子容量都大，直接跳过。
        cnt +=1
        sum_ += money[i]
        del num[idx]
        if cnt == n:   # 桌子用完了就跳出，
            break
print  sum_

发表于 2017-08-26 11:05:22 回复(0)
Python
周昆头像 周昆 
def search(nums, target):
	if target <= nums[0]:
		return 0
	if target > nums[-1]:
		return -1
	l, r = 0, len(nums)-1
	while l+1 != r:
		m = (l+r) // 2
		if target <= nums[m]:
			r = m
		else:
			l = m
	return r

n, m = map(int, raw_input().split())
a = map(int, raw_input().split())
guest = []
for i in range(m):
	guest.append(map(int, raw_input().split()))
guest.sort(key = lambda t:t[1], reverse = True)
a.sort()
i = 0
val = 0
for j in range(m):
	index = search(a, guest[j][0])
	if index >= 0:
		i += 1
		val += guest[j][1]
		del a[index]
		if i == n:
			break
print val
主要思想和其他人一样。不过就找桌子这一点，既然桌子已经排列了。就用二分法找桌子。
这里
函数search 就是一个用二分法找对应最佳桌子的（恰好容纳客人，比它小的桌子无法容纳）
找到桌子我就从array/list删除那桌子
以后会加注释。这一次就懒了
编辑于 2017-04-23 15:48:00 回复(7)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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