题解 | GourmetGrazers-牛客假日团队赛6K题

K-Gourmet Grazers_牛客假日团队赛6

https://ac.nowcoder.com/acm/contest/993/K

题目描述

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 $A_i (1 ≤ A_i ≤ 1,000,000,000)$ and with a greenness score at least $B_i (1 ≤ B_i ≤ 1,000,000,000)$ . The GGG store has $M (1 ≤ M ≤ 100,000)$ different types of grass available, each with a price $C_i (1 ≤ C_i ≤ 1,000,000,000)$ and a greenness score of $D_i (1 ≤ D_i ≤ 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: $A_i$ and $B_i$
* Lines N+2..N+M+1: Line i+N+1 contains two space-separated integers: $C_i$ and $D_i$

输出描述:

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

示例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.

解答

贪心+multiset

本题每一头奶牛有两个标准来找到它合适的牧草。为了使花费最小，当然是选择的两个参数值越小越好。

而且这两个参数是绑定在一起的，所以考虑用pair存数据（pair在库里别忘了qwq）。

首先找到最小符合的牧草，再把这个牧草相关数据从set里删除。

我们可以以其中一个参数为主关键字，按要求从高到低来处理奶牛的要求，每当现在指针所指的牧草能够满足要求，我们就把它的另一参数加入我们的multiset中，加入完成之后multiset会自动维护好当前的最优值。倒着处理可以避免预先加入了不合当前奶牛要求的牧草，保证了正确性，从而降低了处理的代码复杂度。

这里维护有一个也不能说上是技巧的小技巧：

因为我们的pair是默认以first为主关键字升序排序的，而我们要求输出的是其中一个参数：价格的和。因为我们在操作中是把两个参数的一个参数加入multiset维护，所以显而易见的，要得到所有选取的牧草的价格，我们只要把牧草变为pair中的second就可以了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <algorithm>
#include <utility>
typedef long long LL;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;}
const int N=101000;
int n,m;
std::pair<int,int> cow[N],grass[N];
using namespace std;
int main(){
    int i,j;
    n=read();m=read();
    for (i=1;i<=n;++i){cow[i].second=read();cow[i].first=read();}
    sort(cow+1,cow+n+1);
    for (i=1;i<=m;++i){grass[i].second=read();grass[i].first=read();}
    sort(grass+1,grass+m+1);
    multiset<int> G;j=m;LL ans=0;
    for (i=n;i>=1;--i){
        for (;j&&(grass[j].first>=cow[i].first);--j) G.insert(grass[j].second);
        multiset<int>::iterator iter;
        iter=G.lower_bound(cow[i].second);//因为默认以first为主关键字 
        if (iter==G.end()) {puts("-1");return 0;}
        ans+=(*iter);G.erase(iter);
    }
    printf("%lld\n",ans);
    return 0;
}

来源：KAMIKI_横