P1083. 借教室

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 601 阅读时长 ≈ 2 分钟

考点

  • 差分
  • 线段树
  • 二分

题解

见思路

思路

本题的最优解实际上是线段树，但是也有巧妙的解法。

差分+二分

设需要修改订单的申请人编号为idx，能发现答案二分的单调性：

  • 如果idx大于真实答案，订单无法满足
  • 如果idx小于真实答案，订单可以满足

所以直接二分答案，每次用差分批量修改区间，并求差分数组的前缀和来验证答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
int n, m, b[maxn];
ll diff[maxn];

struct node {
  int d_, s_, t_;
} a[maxn];

bool check(int idx) {
  memset(diff, 0, sizeof(diff));
  for (int i = 1; i <= idx; ++i) {
    diff[a[i].s_] += a[i].d_;
    diff[a[i].t_ + 1] -= a[i].d_;
  }
  for (int i = 1; i <= n; ++i) {
    diff[i] += diff[i - 1];
    if (diff[i] > b[i]) return false;
  }
  return true;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> b[i];
  for (int i = 1; i <= m; ++i) cin >> a[i].d_ >> a[i].s_ >> a[i].t_;
  if (check(m + 1)) {
    cout << 0;
    return 0;
  }
  int l = 1, r = m;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << -1 << endl << l;
  return 0;
}

线段树

维护区间最小值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
int n, m;
ll arr[maxn];

struct node {
  int l_, r_;
  ll mi_, lz_;
} seg[4 * maxn];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define l(x) seg[x].l_
#define r(x) seg[x].r_
#define mi(x) seg[x].mi_
#define lz(x) seg[x].lz_

void up(int rt) { mi(rt) = min(mi(lson), mi(rson)); }

void down(int rt) {
  if (lz(rt)) {
    mi(lson) += lz(rt), mi(rson) += lz(rt);
    lz(lson) += lz(rt), lz(rson) += lz(rt);
    lz(rt) = 0;
  }
}

void build(int rt, int l, int r) {
  l(rt) = l, r(rt) = r;
  if (l == r) {
    mi(rt) = arr[l];
    return;
  }
  int mid = (l + r) / 2;
  build(lson, l, mid), build(rson, mid + 1, r);
  up(rt);
}

void update(int rt, int L, int R, ll v) {
  if (L <= l(rt) && r(rt) <= R) {
    mi(rt) += v, lz(rt) += v;
    return;
  }
  down(rt);
  int mid = (l(rt) + r(rt)) / 2;
  if (L <= mid) update(lson, L, R, v);
  if (R > mid) update(rson, L, R, v);
  up(rt);
}

ll query(int rt, int L, int R) {
  if (L <= l(rt) && r(rt) <= R) return mi(rt);
  down(rt);
  ll res = INT_MAX;
  int mid = (l(rt) + r(rt)) / 2;
  if (L <= mid) res = min(res, query(lson, L, R));
  if (R > mid) res = min(res, query(rson, L, R));
  return res;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> arr[i];
  build(1, 1, n);
  ll d, s, t, res;
  for (int i = 1; i <= m; ++i) {
    cin >> d >> s >> t;
    if (d <= query(1, s, t)) {
      update(1, s, t, -d);
    } else {
      cout << -1 << endl << i;
      return 0;
    }
  }
  cout << 0;
  return 0;
}