文章目录

洛谷 P2869 Gourmet Grazers G 做题笔记

发布于

题意

有 $n$ 只奶牛和 $m$ 个食物,第 $i$ 个食物有价格 $c_i$ 和美味度 $d_i$。
第 $i$ 只奶牛要求吃一个价格至少为 $a_i$ 且美味度至少为 $b_i$ 的食物。
问最少花费。无解输出 -1

题解

这是一个二维的问题,我们可以把其中一维排序,这个问题就变成了一维。
所以我们可以按照美味度排序,然后按美味度从大到小枚举奶牛。
对于奶牛 $i$,我们把所有满足美味度不小于 $b_i$ 的所有食物全部扔进一个 multiset 里,然后二分一个价格大于等于 $a_i$ 的食物。如果没有这样的食物,则是无解。

代码

// Please submit with C++14! It's best to use C++20 or higher version.
#ifndef LOCAL        // Spectre
#pragma region HEAD  // By rbtree (https://rbtr.ee)
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &la), la)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)

typedef long long tp;
tp la;
using namespace std;
#ifndef LOCAL
#pragma endregion HEAD
#endif

constexpr bool __MTCS__ = 0;

////////////////////////////////////////////////////////////////////////////////

void __Cored__([[maybe_unused]] tp __TID__) {
  tp n = ra, m = ra, j = 1, c = 0;
  vector<pair<tp, tp>> a(n + 1), b(m + 1);
  multiset<tp> k;
  for (tp i = 1; i <= n; ++i) {
    a[i].second = ra;
    a[i].first = ra;
  }
  for (tp i = 1; i <= m; ++i) {
    b[i].second = ra;
    b[i].first = ra;
  }
  stable_sort(a.begin() + 1, a.end(), greater<pair<tp, tp>>());
  stable_sort(b.begin() + 1, b.end(), greater<pair<tp, tp>>());
  for (tp i = 1; i <= n; ++i) {
    while (j <= m && b[j].first >= a[i].first) {
      k.insert(b[j++].second);
    }
    if (k.lower_bound(a[i].second) == k.end()) {
      puts("-1");
      return;
    }
    c += *k.lower_bound(a[i].second);
    k.erase(k.lower_bound(a[i].second));
  }
  printf("%lld\n", c);
}

////////////////////////////////////////////////////////////////////////////////

signed main() {
  static tp __TCS__ = __MTCS__ ? ra : 1, __NOW__ = 0;
  while (__NOW__ < __TCS__) {
    __Cored__(++__NOW__);
  }
  return 0;
}

暂无评论

发表评论