洛谷P3045

我可能不会贪心

`

#include <bits/stdc++.h>
#define pli pair<LL, int>
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
typedef long long LL;
const int MAXN = 50000;
using namespace std;

priority_queue < pii, vector < pii >, greater < pii > > c;
priority_queue < pii, vector < pii >, greater < pii > > e;
priority_queue < int, vector < int >, greater < int > > re;
bool used[MAXN + 5];

int n, k, p[MAXN + 5], a[MAXN + 5];
LL m;

void init() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> k >> m;  
  for (int i = 1; i <= n; ++i) {
    cin >> p[i] >> a[i];
    c.push(mp(a[i], i));
    e.push(mp(p[i], i));
  }
  for (int i = 1; i <= k; ++i) re.push(0);
}

int main() {
#ifdef forever23
  freopen("test.in", "r", stdin);
#endif
  init();

  int ans = 0;
  while (m > 0 && ans < n) {
    while (!c.empty() && used[c.top().se]) c.pop();
    while (!e.empty() && used[e.top().se]) e.pop();

    int cost = c.top().fi + re.top();

    if (cost < e.top().fi) {
      if (m < cost) break;
      m -= cost;
      re.pop();
      re.push(p[e.top().se] - a[c.top().se]);
      used[c.top().se] = true;
    } else {
      if (m < e.top().fi) break;
      m -= e.top().fi;
      used[e.top().se] = true;
    }

    ++ans;
  }

  cout << ans << endl;
  return 0;
}

本博客所有文章均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处
本文链接:https://23forever.com/2019/07/23/luogu3045/