「EZEC-8」Clear Up 题解

· · 题解

点 i 施加 k 的能量值后影响区间[i-k,i+k]，有等腰直角三角形性质的信息。

因此，本题有一个形象且等价化的表述：

有n(1\leq n\leq 10^6)个由同一数轴上整点构成的底边的等腰直角三角形，尝试用若干个底边仍由该数轴上整点构成的三角形框住，最小化这些直角三角形底边上高的和。

我们认为两个由同一数轴上整点构成的底边的等腰直角三角形有三种关系：相离（完全没有公共点）、相切（恰有一个公共点）、相交（有无数个公共点）。

等腰直角三角形底边上的高之和不够简洁，我们尝试将二维问题一维化，将等腰直角三角形底边上的高和等于等腰直角三角形底边长和的一半。

将问题转化到一维数轴上时，我们发现，本题的实质是一个线段覆盖问题：

有 n(1\leq n\leq 10^6) 条线段[l_i,r_i]，求线段覆盖总长度。

有一个细节需要注意：

每个线段单独计算，若是奇数则需要除以 2 后上取整；若是偶数则直接除以 2 , 无需上取整操作。

下面程序时间复杂度是O(n log_2 n)，仅仅提供一个新思路，希望有抛砖引玉的效果，如有疏漏还请多多指教。

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 1e6 + 10;

struct rec {
    int l, r;
};
rec a[N];

bool cmp(rec x, rec y) {
    if (x.l != y.l)
        return x.l < y.l;
    else
        return x.r > y.r;
}

inline int read() {
    int X = 0, w = 0;
    char c = 0;
    while (!(c >= '0' && c <= '9'))
        w |= c == '-', c = getchar();
    while (c >= '0' && c <= '9')
        X = (X << 1) + (X << 3) + (c ^ 48), c = getchar();
    return w ? -X : X;
}

signed main() {
    int n = read();
    for (int i = 1; i <= n; i++) {
        int x = read();
        a[i].l = i - x, a[i].r = i + x;
    }
    sort(a + 1, a + 1 + n, cmp);
    int nowl = a[1].l, nowr = a[1].r, ans = 0;
    for (int i = 2; i <= n; i++) {
        if (a[i].r <= nowr)
            continue;
        if (a[i].l <= nowr) {
            nowr = a[i].r;
            continue;
        }
        ans += (nowr - nowl) / 2;
        if ((nowr - nowl) % 2 == 1)
            ans++;
        nowl = a[i].l, nowr = a[i].r;
    }
    ans += (nowr - nowl) / 2;
    if ((nowr - nowl) % 2 == 1)
        ans++;
    printf("%lld\n", ans);
    return 0;
}