滴滴内推题-餐馆

╰+攻爆jí腚メ 2022-06-09 03:43 280阅读 0赞

时间限制：1秒

空间限制：32768K

某餐馆有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

##### 输出例子1: #####

##### 20 #####

#include <iostream>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    #include <set>
    using namespace std;
    
    struct node {
    	int num;
    	int val;
    };
    
    bool cmp(const node & p1, const node& p2) {
    	if (p1.val > p2.val || (p1.val == p2.val&&p1.num > p1.num))
    		return true;
    	else
    		return false;
    }
    
    int main() {
    	int n, m;
    	cin >> n >> m;
    	multiset<int> D;
    	for (int i = 0; i<n; i++) {
    		int t;
    		cin >> t;
    		D.insert(t);
    	}
    	vector<node> V;
    	for (int i = 0; i<m; i++) {
    		node temp;
    		cin >> temp.num >> temp.val;
    		V.emplace_back(temp);
    	}
    	sort(V.begin(), V.end(), cmp);
    	long long num=0;
        vector<node>::iterator iter;
    	for (int i = 0; i < m; i++)
    	{
    		set<int>::iterator temp;
    	    temp = D.lower_bound(V[i].num);
    		if (temp != D.end())
    		{
    			num += V[i].val;
    			D.erase(temp);
    		}
    	}
    	cout << num << endl;
    }