「一本通 1.1 例 2」种树

https://loj.ac/problem/10001

Analysis

从前往后种树，如果之前种过，那么就可以skip掉。如果还有要求没有达成，那么从后往前继续遍历，添加未种的地方。 e.g. x01000x010100101001 在x x中需要种三颗树：b = 0, e = 5, t = 3 x01011x010100101001 b = 1, e = 6, t = 4 0x10110x10100101001

Time: $O(h \times max(e - a))$

Code

/*
 * 种树.cpp
 * Copyright (C) 2020 Haoyang <[email protected]>
 *
 * Distributed under terms of the MIT license.
 */
#include <bits/stdc++.h>

using namespace std;

struct line {
  int b, e, t;
} a[5010];

bool used[30010];

int main(int argc, char* argv[]) {
  int n, h;
  cin >> n >> h;
  for (int i = 0; i < h; ++i) {
    cin >> a[i].b >> a[i].e >> a[i].t;
  }
  sort(a, a + h, [](const line& l, const line& r) { return l.e < r.e; });// sort by finish time
  int res = 0;
  for (int i = 0; i < h; ++i) {
    int cnt = 0;
    for (int j = a[i].b; j <= a[i].e; ++j) { // first check if already satified
      if (used[j]) cnt++;
    }
    if (cnt < a[i].t) {
      for (int j = a[i].e; j >= a[i].b && cnt < a[i].t; --j) {
        if (!used[j]) {
          used[j] = 1;
          cnt++;
          res++;
        }
      }
    }
  }
  cout << res;
  return 0;
}

---

Last update: January 9, 2021