题目描述
某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大
#include <stdio.h> #include <algorithm> #include <vector> #include <queue> # define f(i,m,n) for(int i=m; i<=n; i++) # define sf(x) scanf("%d", &x) using namespace std; typedef long long int ll; struct cus { int m, b; }; struct cmp { bool operator()(cus a, cus b) { return a.m < b.m; } }; int _cmp(cus a, cus b) { return a.b < b.b; } priority_queue<cus, vector<cus>, cmp> q; int a[500010]; cus b[500010]; int main() { int n, m; sf(n);sf(m); f(i, 1, n) sf(a[i]); while (!q.empty())q.pop(); ll sum = 0; f(i, 1, m) { sf(b[i].b);sf(b[i].m); } sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + m, _cmp); int j = 1; f(i, 1, n) { for (; j <= m; j++) if (a[i] >= b[j].b) q.push(b[j]); else break; if (q.empty()) continue; else { sum = sum + q.top().m; q.pop(); } } printf("%lld", sum); return 0; }
