CTSC2018 混合果汁

要求最小美味度最大,很显然可以二分。那么二分之后用主席树贪心 check 就行了。

#include <iostream>
#include <cstdio>
#include <algorithm>

typedef long long LL;
#define int LL

const int MAXN = 100000;

int n, m;

struct Juice {
  int d, p, l;
  Juice() : d(0), p(0), l(0) {}
  Juice(int _d, int _p, int _l) : d(_d), p(_p), l(_l) {}
  friend bool operator< (const Juice &lhs, const Juice &rhs) {
    return lhs.d > rhs.d;
  }
} a[MAXN | 1];

namespace persistentSegmentTree {
  struct Node {
    int sumv, cnt;
    Node *ch[2];
    Node() : sumv(0), cnt(0) {
      ch[0] = ch[1] = NULL;
    }
  } *root[MAXN | 1];
  Node *build(int l, int r) {
    Node *now = new Node;
    if (l == r) return now;
    int mid = (l + r) >> 1;
    now -> ch[0] = build(l, mid);
    now -> ch[1] = build(mid + 1, r);
    return now;
  }
  Node *insert(Node *o, int l, int r, int pos, int cnt) {
    Node *now = new Node;
    now -> cnt = o -> cnt + cnt;
    now -> sumv = o -> sumv + pos * cnt;
    if (l == r) return now;
    int mid = (l + r) >> 1;
    now -> ch[0] = o -> ch[0];
    now -> ch[1] = o -> ch[1];
    if (pos <= mid) now -> ch[0] = insert(o -> ch[0], l, mid, pos, cnt);
    else now -> ch[1] = insert(o -> ch[1], mid + 1, r, pos, cnt);
    return now;
  }
  int query(Node *o, int l, int r, int k) {
    if (l == r) return k * l;
    int mid = (l + r) >> 1;
    if (o -> ch[0] -> cnt >= k) return query(o -> ch[0], l, mid, k);
    else return o -> ch[0] -> sumv + query(o -> ch[1], mid + 1, r, k - o -> ch[0] -> cnt);
  }
}

using namespace persistentSegmentTree;

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

bool check(int lim, int g, int l) {
  Node *o = root[lim];
  if (o -> cnt < l) return 0;
  int res = query(o, 1, MAXN, l);
  if (res > g) return 0;
  return 1;
}

signed main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) {
    a[i].d = read();
    a[i].p = read();
    a[i].l = read();
  }
  root[0] = build(1, MAXN);
  std::sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; ++i) root[i] = insert(root[i - 1], 1, MAXN, a[i].p, a[i].l);
  while (m--) {
    int g = read(), ll = read();
    int l = 1, r = n, mid, res = -1;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (check(mid, g, ll)) {
        res = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    printf("%lld\n", res == -1 ? -1 : a[res].d);
  }
  return 0;
}
最后修改:2019 年 10 月 04 日 10 : 29 PM

发表评论