题目描述某餐馆有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范围内。 输出描述:输出一个整数,表示最大的总预计消费金额 /////////////////////// 链接：https://www./questionTerminal/d2cced737eb54a3aa550f53bb3cc19d0 来源：牛客网 #include <iostream>#include <string>#include <vector>#include <algorithm>#include <set>struct guest { int num; int money;};bool cmp(guest a, guest b) { if (a.money == b.money) { return a.num < b.num; } return a.money > b.money;}int main() { using namespace std; int n, m; while (cin >> n >> m) { multiset<int> desk; vector<guest> people(m); long long ans = 0; for (int i = 0; i < n; i++) { int temp; cin >> temp; desk.insert(temp); } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; people[i].num = a; people[i].money = b; } sort(people.begin(), people.end(), cmp); for (int i = 0; i < m; i++) { if (desk.empty()) { break; } if (people[i].num <= *desk.rbegin()) { ans += people[i].money; desk.erase(desk.lower_bound(people[i].num)); } } cout << ans << endl; } return 0;}////////////////// 自己动手///// //////////////////// #include <iostream> #include <string> #include <vector> #include <algorithm> #include <set> using namespace std; struct customer { int number; int money; }; bool compare(customer &a,customer&b) { if(a.money==b.money) return a.number<b.number; return a.money>b.money; } int main() { int n,m; while(cin>>n>>m) { multiset<int>desk; int temp; for(int i=0;i<n;i++) { cin>>temp; desk.insert(temp); } vector<customer>people(m); for(int i=0;i<m;i++) { int a,b; cin>>a>>b; people[i].number=a; people[i].money=b; } sort(people.begin(),people.end(),compare); int ans=0; for(int i=0;i<m;i++) { if(desk.empty()) break; if(people[i].number<=*desk.rbegin()) { ans+=people[i].money; //desk.erase(desk.lower_bound(people[i].num)); desk.erase(desk.lower_bound(people[i].number)); } } cout<<ans<<endl; } return 0; } 1
|
|
|
