CSES 1143 Hotel Queries 做题笔记

发布于

题意

给定 $n$ 个数,编号为 $1$ 到 $n$。$m$ 次操作,每次操作给定一个 $x$,询问编号最小的大于等于 $x$ 的数。若没有则输出 $0$,若有则输出位置,并将该位置上的数减去 $x$。

$1 \leq n, m \leq 2 \times 10^5$

题解

这里提供两个做法。

做法 1

大力分块。每次暴力循环遍历每个块,直到找到一个块,使得这个块中的最大值大于等于 $x$。

然后在这个块里遍历,找到那个位置。然后这个位置上的数减去 $x$,暴力更新块内最大值。

时间复杂度:$\mathcal O\left(m \sqrt n\right)$

代码:

constexpr tp Hat_N = 2e5 + 3, Hat_SQN = 321;

tp a[Hat_N], bid[Hat_N], bans[Hat_SQN], bl[Hat_SQN], br[Hat_SQN], btag[Hat_SQN];

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n, m, B; bin >> n >> m; B = sqrt(n) + .5;
  for (tp i = 1; i <= n; ++i) {
    bid[i] = (i - 1) / B + 1;
    if (!bl[bid[i]]) bl[bid[i]] = i;
    br[bid[i]] = i;
    bin >> a[i];
    bans[bid[i]] = max(bans[bid[i]], a[i]);
  }
  while (m--) {
    tp x, loc = -1; bin >> x;
    for (tp i = 1; i <= bid[n]; ++i) {
      if (bans[i] >= x) { loc = i; break; }
    }
    if (loc == -1) { bin << "0 "; continue; }
    for (tp i = bl[loc]; i <= br[loc]; ++i) {
      if (a[i] >= x) {
        bin << i << ' ';
        a[i] -= x; bans[loc] -= x;
        for (tp j = bl[loc]; j <= br[loc]; ++j) bans[loc] = max(bans[loc], a[j]);
        break;
      }
    }
  }
  bin << '\n';
}

做法 2

线段树二分。这个很模版,但是没有分块好写(


暂无评论

发表评论