某餐馆有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范围内。
分析：
采用贪心法。先把顾客进行消费金额降序，如果消费金额相等，则按照人数升序排序。 然后枚举每波顾客去二分当前最适合的桌子的容量。时间复杂度：O(mlogm + nlogm)
Read full article from 餐馆就餐问题 - ljp1919的专栏 - CSDN博客
No comments:
Post a Comment