题目链接：https://ac.nowcoder.com/acm/contest/993/K/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Like so many others, the cows have developed very haughty tastes and will no longer graze on just any grass. Instead, Farmer John must purchase gourmet organic grass at the Green Grass Grocers store for each of his N (1 ≤ N ≤ 100,000) cows.
Each cow i demands grass of price at least Ai (1 ≤ Ai ≤ 1,000,000,000) and with a greenness score at least Bi (1 ≤ Bi ≤ 1,000,000,000). The GGG store has M (1 ≤ M ≤ 100,000) different types of grass available, each with a price Ci (1 ≤ Ci ≤ 1,000,000,000) and a greenness score of Di (1 ≤ Di ≤ 1,000,000,000). Of course, no cow would sacrifice her individuality, so no two cows can have the same kind of grass.
Help Farmer John satisfy the cows' expensive gourmet tastes while spending as little money as is necessary.

输入描述

* Line 1: Two space-separated integers: N and M.
* Lines 2..N+1: Line i+1 contains two space-separated integers: Ai and Bi
* Lines N+2..N+M+1: Line i+N+1 contains two space-separated integers: Ci and Di

输出描述

* Line 1: A single integer which is the minimum cost to satisfy all the cows. If that is not possible, output -1.

输入

4 7
1 1
2 3
1 4
4 2
3 2
2 1
4 3
5 2
5 4
2 6
4 4

输出

12

说明

Cow 1 eats grass 2 at cost 2, cow 2 eats grass 3 at cost 4, cow 3 eats grass 6 at cost 2, and cow 4 eats grass 7 at cost 4, for a total cost of 12.

解题思路

题意:有N头牛与M种草，给定第i头要吃的草的最低价格为Ai，草的最低质量为Bi。M种草每种草的价格为Ci，质量为Di。同时每头牛吃的草的种类要不同，问使得每头牛都吃到满足条件的草所需要花费的最少价格?
思路:记录牛要吃的草的要求和草的规格，均按照草的质量从大到小排序。通过枚举排序后的数组,把满足牛最低质量的都存进set里面，然后从中找出满足最低价格的最小值，记录对答案的贡献，并从集合中删除该数。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct edge {
    int pri, qua;
    bool operator < (const edge & s) const {
        if (s.qua != qua)
            return s.qua < qua;
        return s.pri > pri;
    }
}spta[MAXN], sptb[MAXN];
int main() {
    int n, m;
    long long ans;
    while (~scanf("%d%d", &n, &m)) {
        ans = 0;
        multiset <int> spt;
        for (int i = 0; i < n; i++)
            scanf("%d%d", &spta[i].pri, &spta[i].qua);
        for (int i = 0; i < m; i++)
            scanf("%d%d", &sptb[i].pri, &sptb[i].qua);
        sort(spta, spta + n);
        sort(sptb, sptb + m);
        int j = 0;
        multiset <int>::iterator it;
        for (int i = 0; i < n && ~ans; i++) {
            while  (j < m && sptb[j].qua >= spta[i].qua)
                spt.insert(sptb[j++].pri);
            it = spt.lower_bound(spta[i].pri);
            if (it != spt.end()) {
                ans += *it;
                spt.erase(it);
            }
            else ans = -1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}