P1873【COCI 2011+2012 5】EKO 砍树¶

T15:20:00+08:00 看到这么多二分，我来发一篇差分的。其实只有 \(O(n)\)。

假如有这么一组树：

Text Only
1	`10 6 12 6 9 3 9`

把树倒过来看：

Text Only
1 2 3 4 5 6 7	`1 \| # # # # # # # # # # 2 \| # # # # # # 3 \| # # # # # # # # # # # # 4 \| # # # # # # 5 \| # # # # # # # # # 6 \| # # # 7 \| # # # # # # # # #`

那么很显然如果我在高度 \(7\) 切，将是这样：

Text Only
1 2 3 4 5 6 7 8	`1 2 3 4 5 6 7 \| 8 9 10 11 12 1 \| # # # # # # # \| # # # 2 \| # # # # # # \| 3 \| # # # # # # # \| # # # # # 4 \| # # # # # # \| 5 \| # # # # # # # \| # # 6 \| # # # \| 7 \| # # # # # # # \| # #`

如果我把树横着叠起来（对每一列计数求和）：

Text Only

      1 2 3 4 5 6 7 | 8 9 10 11 12
sum | 7 7 7 6 6 6 4 | 4 4  2  1  1
  1 | # # # # # # # | # #  #
  2 | # # # # # #   |
  3 | # # # # # # # | # #  #  #  #
  4 | # # # # # #   |
  5 | # # # # # # # | # #
  6 | # # #         |
  7 | # # # # # # # | # #

那么不就变成求个后缀和，直到求和到某一个高度 \(h\) 下满足要求，就要在 \(h-1\) 锯么。

于是就变成了 区间加 & 后缀和。（当然你反着存用前缀和也行）

那最简单的区间加就是利用差分数组了吧：

dif[i] = a[i] - a[i-1]

对 \(a\) 的 \([l, r]\) 区间加上 \(k\) 也就是：

dif[l] += k，dif[r+1] -= k。

然后求一边前缀和就是原数组啦。（当然你要是反着差的分就后缀和）

码：

C++
#include <iostream>

using namespace std;

const int MAXN = 1E6;

long long differ[MAXN + 2];

void add(int l, int r) {
    differ[l]++;
    differ[r+1]--;
}

int main () {
    int N, M; cin >> N >> M;

    int maxL = 0;
    for (int i = 1, l; i <= N; i++) {
        cin >> l;
        maxL = max(maxL, l);
        add(1, l);
    }

    for (int i = 1; i <= maxL + 1; i++) {
        differ[i] += differ[i-1];
    }
    for (int i = maxL; i >= 1; i--) {
        differ[i] += differ[i+1];
        if (differ[i] >= M) {
            cout << i-1 << endl;
            break;
        }
    }

    return 0;
}

P1873【COCI 2011+2012 5】EKO 砍树¶

评论