题解：美食鉴赏家奶牛（Gourmet Grazers）

题目描述

农场有 $N$ 头奶牛，每头奶牛需要食用一种草，要求草的价格至少为 $A_i$，绿色度至少为 $B_i$。商店有 $M$ 种草，每种草的价格为 $C_j$，绿色度为 $D_j$，且每种草只能被一头奶牛食用。求满足所有奶牛需求的最小总花费，若无法满足则输出 $-1$。

算法思路

问题的核心是为每头奶牛匹配满足条件（价格$≥A_i$、绿色度$≥B_i$）的最便宜的草，且每草只能用一次。关键步骤如下：

1. 排序策略：

   • 将奶牛按绿色度 $B_i$ 降序排序（优先处理绿色度要求高的奶牛）。
   • 将草按绿色度 $D_j$ 降序排序（确保在处理某头奶牛时，所有绿色度足够的草已被考虑）。

2. 贪心匹配：

   • 维护一个 $multiset$（有序集合），动态存储当前绿色度足够的草的价格。
   • 对于每头奶牛，在 $multiset$ 中查找价格≥其要求的最小价格草，若找到则累加费用并移除该草；若未找到则输出 $-1$。

复杂度分析

• 时间复杂度：

  • 排序：$O(N log N + M log M)$。
  • 插入、查询、删除操作：每个草最多被处理一次，每次操作 $O(log M)$，总时间复杂度$O((N + M) log M)$，适用于题目数据规模$（N, M ≤ 1e5）$。

• 空间复杂度：

  • $O(M)$，用于存储草的集合。

标程

#include <cstdio>
#include <set>
#include <algorithm>
#define maxn 100005
using namespace std;

struct Detail {
    int price;   // 价格（奶牛为下限，草为实际价格）
    int fresh;   // 绿色度（奶牛为下限，草为实际值）
    int id;      // 标识（用于去重，本题非必需）
};

int n, m;
long long ans = 0;  // 初始化为0，成功时累加

// 按绿色度降序排序（处理绿色度高的优先）
bool cmp_fresh(const Detail& a, const Detail& b) {
    return a.fresh > b.fresh;
}

// multiset比较规则：按价格升序排列
struct cmp_price {
    bool operator()(const Detail& a, const Detail& b) const {
        return a.price < b.price;
    }
};

multiset<Detail, cmp_price> grassSet;  // 维护当前可用草的价格

void solve() {
    int j = 1;  // 当前处理到的草的下标
    sort(cow + 1, cow + n + 1, cmp_fresh);      // 奶牛按绿色度降序
    sort(grass + 1, grass + m + 1, cmp_fresh);  // 草按绿色度降序

    for (int i = 1; i <= n; ++i) {
        // 将绿色度≥当前奶牛需求的草加入集合
        while (j <= m && grass[j].fresh >= cow[i].fresh) {
            grassSet.insert(grass[j]);
            ++j;
        }

        // 查找价格≥当前奶牛需求的最小价格草
        Detail target = cow[i];
        auto it = grassSet.lower_bound(target);
        if (it == grassSet.end()) {  // 无满足条件的草
            ans = -1;
            return;
        }

        // 累加费用并移除已使用的草
        ans += it->price;
        grassSet.erase(it);
    }
}

Detail cow[maxn], grass[maxn];  // 奶牛和草的数组

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &cow[i].price, &cow[i].fresh);
        cow[i].id = i;  // 标识可省略，本题不需要
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &grass[i].price, &grass[i].fresh);
        grass[i].id = i;  // 标识可省略，本题不需要
    }

    solve();
    printf("%lld\n", ans);  // 输出结果
    return 0;
}