[每日一题] [NC50995] Supermarket

题目大意：有很多物品，每个物品有一个价值和deadline，放入每个物品需要1 unit time，最多可以购买多少总价值。

https://ac.nowcoder.com/acm/problem/50995

看了一下我的做法似乎和大家的不太一样，原来和之前某一道题类似是带反悔的贪心。

我的做法，就是将物品按照价值从大到小排序，然后每次将一个物品插入deadline之前最后那个空着的时间。这样应该比较直观是最优解，因为如果某个物品价值比后面都高，而且还能合法的插入，那么就应该选择它比较合算，否则总能替换成该物品。

难点是如何实现找到<=deadline的最大值，并且能删除一个值。刚开始用的是set<int>和std::lower_bound但是蜜汁TLE，所以想了一下用一个binary indexed tree maintain插入的数，只要寻找rightmost index, s.t. index到deadline之间的插入个数< deadline - index + 1，可以用二分。时间复杂度应该是每个样例O(n log^2(T))。我用了单个BIT然后每次撤回之前的操作，即使不用也可以AC。</int>

struct BIT {
  VL tree;
  int N;
  BIT(int N) : N(N), tree(N + 1, 0) {}
  // add v to value at x
  void add(int x, int v) {
    assert(x >= 0 && x <= N);
    ++x;
    while(x <= N) {
      tree[x] += v;
      x += (x & -x);
    }
  }
  // get cumulative sum up to and including x
  ll getsum(int x) {
    assert(x >= 0 && x <= N);
    ++x;
    ll res = 0;
    while(x) {
      res += tree[x];
      x -= (x & -x);
    }
    return res;
  }
};
int N;
#define MAXN 10005
BIT bit(MAXN);
ll doit(VPII& products) {
  sort(ALL(products), greater<PII>());
  ll ans = 0;
  VI erased;
  for (const PII& p : products) {
    int deadline = p.SE;
    int value = p.FI;
    // Search for rightmost i, s.t. sum of i to deadline < deadline - i + 1.
    int lo = 1, hi = deadline;
    if (bit.getsum(deadline) == deadline) continue;
    while (lo < hi) {
      int mi = RMID(lo, hi);
      if (bit.getsum(deadline) - (mi?bit.getsum(mi - 1):0) < deadline - mi + 1) {
        lo = mi;
      } else {
        hi = mi - 1;
      }
    }
    int to_add = lo;
    ans += value;
    erased.PB(to_add);
    bit.add(to_add, 1);
  }
  for (int x : erased) bit.add(x, -1);
  return ans;
}
int main(int argc, char* argv[]) {
  while (scanf("%d", &N) > 0) {
    readvpii(products, N);
    print(doit(products));
  }
  return 0;
}