某餐館有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 }