滴滴出行2017秋招笔试真题-编程题汇总 [编程题]餐馆

题目链接： [编程题]餐馆

解题思路：

   想的方法是对的，但是一直超时，要善于使用C++的容器

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool cmp(const pair<int, int> &A, const pair<int, int> &B) {
    if(A.second != B.second) {
        return A.second > B.second;
    }
    return A.first > B.first;
}
int main() {
    int n, m;
    cin >> n >> m;
    mulitiset<int> a;   // 自动排序的集合，可重复
    vector<pair<int, int>> arr;
    for(int i = 0; i < n; i++) {
        int k;
        cin >> k;
        a.insert(k);
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        arr.emplace_back(x, y);
    }
    sort(arr.begin(), arr.end(), cmp);  // 排序
    ll ans = 0;
    for(int i = 0; i < m && a.size() > 0; i++) {
        auto it = a.lower_bound(arr[i].first); // 二分查找大于等于这桌人数
        if(it != a.end()) {
            ans += arr[i].second;  // 加上这桌钱
            a.erase(it);         // 删掉这个元素
        }
    }
    cout << ans << endl;
    return 0;
}