某餐馆有n张桌子，每张桌子有一个参数：a可容纳的最大人数；有m批客人，每批客人有两个参数：b人数、c预计消费金额。在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大。
输入描述
输入包括m+2行。
第一行包括2个整数n(1<=n<=50000)，m(1<=m<=50000);
第二行为n个参数a，即每个桌子可容纳的最大人数，以空格分隔，范围均在32位int范围内;
接下来m行，每行两个参数b和c，分别表示第i批客人的人数和预计消费金额，以空格分隔，范围均在32位int范围内。
输出描述
输出一个整数，表示最大的总预计消费金额。
输入例子
3 5
2 4 2
1 3
3 5
3 7
5 9
1 10
输出例子
20
算法思路：贪心法解，把桌子按大小由小到大排序，把顾客批次按价格由大到小排序。然后顺次遍历桌子，每次选定桌子后顺次遍历顾客批次，可以的就坐进当前桌子。
C++程序：
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4 using namespace std;
5
6 struct person
7 {
8 int num;
9 int price;
10 };
11
12 bool cmp(person p1, person p2)
13 {
14 return p1.price>p2.price;
15 }
16
17 int main()
18 {
19 int n,m;
20 vector<person> pp;
21
22 cin>>n>>m;
23 vector<int> table;
24 for(int i=0; i<n; i++)
25 {
26 int tab;
27 cin>>tab;
28 table.push_back(tab);
29 }
30 for(int i=0; i<m; i++)
31 {
32 person tmp_p;
33 cin>>tmp_p.num>>tmp_p.price;
34 pp.push_back(tmp_p);
35 }
36
37 sort(pp.begin(), pp.end(), cmp); // from big 2 small
38 sort(table.begin(), table.end()); // from small 2 big
39
40 int total_price=0;
41 for(int i=0; i<table.size(); i++) // from small 2 big
42 {
43 for(int j=0; j<pp.size(); j++) // from big 2 small
44 {
45 if(pp[j].num <= table[i])
46 {
47 total_price += pp[j].price;
48 pp.erase(pp.begin()+j);
49 break;
50 }
51 }
52 }
53
54 cout<<total_price<<endl;
55
56 return 0;
57 }