洛谷 P5019 [NOIP 2018 提高组] 铺设道路

// P5019 [NOIP 2018 提高组] 铺设道路 —— ★ 这一版就能 AC
//
// 题意：n 块区域，第 i 块下陷 d_i。每天可以选一段**连续区间**，让区间里每块的深度减 1，
//       前提是区间内每块的深度都不为 0。问最少几天能全部填平。
//
// ★ 关键一步：答案 = **所有「上升沿」的高度之和**
//
//       ans = Σ max(0, d[i] − d[i−1])      （约定 d[0] = 0）
//
//   证明要两半，缺一半都不算证完（页面第 ② 步）：
//   · **下界**：一天只能选一段连续区间 ⇒ 一天最多让**一个**上升沿降低 1
//     ⇒ 至少需要「上升沿总高度」那么多天；
//   · **上界**：按这个数确实能填完（页面第 ② 步给了构造）。
//
// ⚠ 两处要算一算的地方：
//   ① `d[0] = 0` 这个约定不能省 —— 第一块本身就是一个上升沿；
//   ② 答案最大约 `10⁴ × n/2 = 5 × 10⁸`（相邻 0 / 10⁴ 交替），`int` 够用 ——
//      ★ **算完确认够用，和没算过是两回事**。
//
// 复杂度 `O(n)`，读入 10⁵ 个数，随便怎么读都行。
// ★ 顺带：洛谷 P1969「积木大赛」和这道题是同一道题（问法反过来，答案一模一样）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    long long ans = 0, prev = 0;                    // ★ prev 从 0 开始 —— 这就是 d[0] = 0
    for (int i = 0; i < n; i++) {
        long long d;
        cin >> d;
        if (d > prev) ans += d - prev;              // 只有「升上去」的那一截要单独花天数
        prev = d;
    }
    cout << ans << "\n";
    return 0;
}

// P5019 的第二种解法：**分治** —— 它也是对的，放在这儿当参照物
//
// 想法：在区间 `[l, r]` 里找最矮的那一块（深度 m）。
//   整段先一起降 m 天（这 m 天每天都能选整个区间），剩下的被最矮那块切成若干独立小段，
//   各自递归。⇒ `solve(l, r) = m + Σ solve(每个子段)`。
//
// ★ 它和差分那一行**一个字都不共享** —— 所以它是个像样的参照物。
//
// ⚠⚠ 而它的复杂度**取决于数据形状**，这一点很值得量（页面第 ⑤ 步）：
//   · 随机数据上，最矮的那块大致把区间劈成两半 ⇒ `O(n log n)`；
//   · **单调数列**上，最矮的永远在一头 ⇒ 每次只剥掉一块 ⇒ `O(n²)`，顶格 10¹⁰ 级别。
//   ★ 而随机数据**看不出这件事** —— 这是[第 53 章](/ch/53-hld/)那条
//     「有一类 bug 只坏复杂度不坏答案」的又一次现场。
//
// ⚠ 递归深度也跟着形状走，所以这里写成显式栈，免得单调数据直接爆栈。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> d(n);
    for (auto& x : d) cin >> x;

    long long ans = 0;
    // 栈里存 (l, r, base)：这一段还没被填掉的部分，已经整体降过 base
    vector<array<long long, 3>> st;
    st.push_back({0, (long long)n - 1, 0});
    while (!st.empty()) {
        auto [l, r, base] = st.back();
        st.pop_back();
        if (l > r) continue;
        long long m = LLONG_MAX;
        for (long long i = l; i <= r; i++) m = min(m, d[i]);
        ans += m - base;                            // 这一段整体再降 (m - base) 天
        long long start = l;
        for (long long i = l; i <= r; i++) {
            if (d[i] == m) {                        // 最矮的那些块把区间切开
                if (start <= i - 1) st.push_back({start, i - 1, m});
                start = i + 1;
            }
        }
        if (start <= r) st.push_back({start, r, m});
    }
    cout << ans << "\n";
    return 0;
}

// P5019 错法一：忘了 `max(0, ·)`，直接把差累加起来
//
// ★★ 说清楚它**算了什么**比说它「错了」有用得多 —— 这一版算的是一个望远镜求和：
//
//       Σ (d[i] − d[i−1])  =  d[n] − d[0]  =  d[n]
//
//   也就是说：**它永远输出最后一块的深度**（页面第 ④ 步实测逐组相等）。
//   ⇒ 这个结论一出来，它的所有表现都是白送的推论：
//     · 数列**单调不减**时它是对的（那时候确实没有下降沿）；
//     · 只要出现过一次下降，它就偏小。
//
// ★ 而官方样例 `4 3 2 5 3 5` 最后一块是 5 ⇒ 它输出 5，答案是 9 ⇒ **样例挡住了它**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    long long ans = 0, prev = 0;
    for (int i = 0; i < n; i++) {
        long long d;
        cin >> d;
        ans += d - prev;                            // ← 少了 max(0, ·)
        prev = d;
    }
    cout << ans << "\n";
    return 0;
}

// P5019 错法二：漏掉「`d[0] = 0`」这个约定 —— 从第二块才开始数上升沿
//
// 第一块本身就是从平地（0）升上来的，它那一截也要花天数。
// 漏掉之后，答案正好少了 `d[1]`。
//
// ★★ 而这个 bug 也能一句话说清楚它算了什么：**它算的是「答案 − 第一块的深度」**。
//   ⇒ 只有当第一块是 0 的时候它才对。
// ★ 官方样例第一块是 4 ⇒ 它输出 5，答案 9 ⇒ **样例挡住它**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> d(n);
    for (auto& x : d) cin >> x;
    long long ans = 0;
    for (int i = 1; i < n; i++)                     // ← 从 i = 1 开始，第一块那一截丢了
        if (d[i] > d[i - 1]) ans += d[i] - d[i - 1];
    cout << ans << "\n";
    return 0;
}

// P5019 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p5019Count`      人看的版本
// `./p5019Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★ 三条完全不同的路算出同一个数：差分公式 / 分治 / 一天一天地填；
//   ② ★★ 两个错法**算了什么**（不是「错了」）：一个恒等于最后一块的深度，
//      一个恒等于「答案 − 第一块的深度」；
//   ③ ★★★ 分治那版的复杂度**取决于数据形状** —— 用「比较次数」这把机器无关的尺子量；
//   ④ ★ 顶格答案有多大（`int` 到底够不够，算一遍）；
//   ⑤ ★ 两个错法在随机数据上的抓获率。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

/** 正解：上升沿之和 */
static ll byDiff(const vector<ll>& d) {
    ll ans = 0, prev = 0;
    for (ll x : d) { if (x > prev) ans += x - prev; prev = x; }
    return ans;
}
/** 错法一：忘了 max(0, ·) */
static ll noMax(const vector<ll>& d) {
    ll ans = 0, prev = 0;
    for (ll x : d) { ans += x - prev; prev = x; }
    return ans;
}
/** 错法二：漏掉 d[0] = 0 */
static ll noZero(const vector<ll>& d) {
    ll ans = 0;
    for (size_t i = 1; i < d.size(); i++) if (d[i] > d[i - 1]) ans += d[i] - d[i - 1];
    return ans;
}
/** 第二条路：分治。cmp 记录「找最矮那块」一共比了多少次 —— 机器无关的尺子 */
static ll byDivide(const vector<ll>& d, ll* cmp = nullptr) {
    ll ans = 0;
    if (cmp) *cmp = 0;
    vector<array<ll, 3>> st{{0, (ll)d.size() - 1, 0}};
    while (!st.empty()) {
        auto [l, r, base] = st.back();
        st.pop_back();
        if (l > r) continue;
        ll m = LLONG_MAX;
        for (ll i = l; i <= r; i++) { m = min(m, d[i]); if (cmp) (*cmp)++; }
        ans += m - base;
        ll start = l;
        for (ll i = l; i <= r; i++)
            if (d[i] == m) { if (start <= i - 1) st.push_back({start, i - 1, m}); start = i + 1; }
        if (start <= r) st.push_back({start, r, m});
    }
    return ans;
}
/** 第三条路：一天一天地填（每天挑第一个还没填平的极大连续段）—— 只在小数据上用 */
static ll bySimulate(vector<ll> d) {
    ll days = 0;
    while (true) {
        int i = 0, n = d.size();
        while (i < n && d[i] == 0) i++;
        if (i == n) break;
        int j = i;
        while (j < n && d[j] > 0) j++;
        for (int k = i; k < j; k++) d[k]--;
        days++;
    }
    return days;
}

static vector<ll> gen(mt19937& rng, int n, int dHi, int shape) {
    vector<ll> d(n);
    for (int i = 0; i < n; i++) d[i] = (ll)(rng() % (unsigned)(dHi + 1));
    if (shape == 1) sort(d.begin(), d.end());
    else if (shape == 2) sort(d.rbegin(), d.rend());
    return d;
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ① 三条路一致 */
    {
        mt19937 rng(20260829u);
        int groups = 0, badDiv = 0, badSim = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            vector<ll> d = gen(rng, (int)(rng() % 12) + 1, 10, 0);
            ll ok = byDiff(d);
            if (byDivide(d) != ok) badDiv++;
            if (bySimulate(d) != ok) badSim++;
        }
        if (!CSV) printf("① %d 组：差分公式 vs 分治不一致 %d 组；差分公式 vs 一天一天地填不一致 %d 组\n",
                         groups, badDiv, badSim);
        row("three", {groups, badDiv, badSim});
    }

    /* ② 两个错法「算了什么」 */
    {
        mt19937 rng(5019u);
        int rounds = 300, eqLast = 0, eqMinusFirst = 0;
        for (int r = 0; r < rounds; r++) {
            vector<ll> d = gen(rng, (int)(rng() % 30) + 1, 20, 0);
            if (noMax(d) == d.back()) eqLast++;
            if (noZero(d) == byDiff(d) - d[0]) eqMinusFirst++;
        }
        if (!CSV) printf("② %d 轮：「忘了 max」那版 ≡ 最后一块的深度 %d 轮；"
                         "「漏掉 d[0]=0」那版 ≡ 答案 − 第一块深度 %d 轮\n", rounds, eqLast, eqMinusFirst);
        row("what", {rounds, eqLast, eqMinusFirst});
    }

    /* ③ ★★★ 分治的复杂度取决于形状 —— 数比较次数，不看秒表 */
    {
        const int NS[] = {1000, 4000, 16000};
        vector<ll> out;
        for (int n : NS) {
            mt19937 rng(n * 7919u + 7u);
            ll cRand = 0, cSorted = 0;
            {
                vector<ll> d = gen(rng, n, 10000, 0);
                byDivide(d, &cRand);
            }
            {
                vector<ll> d = gen(rng, n, 10000, 1);        // 单调不减
                byDivide(d, &cSorted);
            }
            out.push_back(cRand); out.push_back(cSorted);
            if (!CSV) printf("③ n = %5d：分治在随机数据上比了 %lld 次，在单调数列上比了 %lld 次"
                             "（差 %.1f 倍）\n", n, cRand, cSorted, (double)cSorted / cRand);
        }
        row("shape", out);
    }

    /* ④ 顶格答案有多大 */
    {
        int n = 100000;
        vector<ll> d(n);
        for (int i = 0; i < n; i++) d[i] = (i % 2) ? 10000 : 0;   // 0 / 10^4 交替 —— 最坏形状
        ll ans = byDiff(d);
        if (!CSV) printf("④ 顶格最坏（n = 10⁵，0 / 10⁴ 交替）：答案 %lld，而 2³¹ = 2147483648 "
                         "⇒ int %s\n", ans, ans < 2147483648LL ? "够用" : "不够");
        row("worst", {ans, 2147483648LL, ans < 2147483648LL ? 1 : 0});
    }

    /* ⑤ 两个错法的抓获率 */
    {
        mt19937 rng(31337u);
        int rounds = 300, a = 0, b = 0;
        for (int r = 0; r < rounds; r++) {
            vector<ll> d = gen(rng, (int)(rng() % 12) + 1, 10, 0);
            ll ok = byDiff(d);
            if (noMax(d) != ok) a++;
            if (noZero(d) != ok) b++;
        }
        if (!CSV) printf("⑤ %d 轮随机：「忘了 max」被抓 %d 次，「漏掉 d[0]=0」被抓 %d 次\n", rounds, a, b);
        row("catch", {rounds, a, b});
    }
    return 0;
}

// P5019 对拍生成器：`./p5019Gen <seed> [n 上限] [d 上限] [形状]`
//   形状：0 = 随机（默认）　1 = 单调不减　2 = 单调不增
//
// ★ 「形状」这个旋钮不是为了抓答案错的 bug —— 两个答案错法在随机数据上就被抓得干干净净。
//   它是为了**量分治那版的复杂度**（页面第 ⑤ 步）：
//   随机数据上最矮的那块大致把区间劈成两半 ⇒ `O(n log n)`；
//   **单调数列上最矮的永远在一头 ⇒ 每次只剥掉一块 ⇒ `O(n²)`**。
//   ⚠ 而这件事**答案是对的**，任何比对答案的对拍都看不见它。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int nHi = argc > 2 ? atoi(argv[2]) : 12;
    int dHi = argc > 3 ? atoi(argv[3]) : 10;
    int shape = argc > 4 ? atoi(argv[4]) : 0;
    nHi = max(1, min(100000, nHi));
    dHi = max(0, min(10000, dHi));

    mt19937 rng(seed * 2654435761u + 19u);
    int n = (int)(rng() % (unsigned)nHi) + 1;
    vector<int> d(n);
    for (int i = 0; i < n; i++) d[i] = (int)(rng() % (unsigned)(dHi + 1));
    if (shape == 1) sort(d.begin(), d.end());
    else if (shape == 2) sort(d.rbegin(), d.rend());

    printf("%d\n", n);
    for (int i = 0; i < n; i++) printf("%d%c", d[i], i + 1 == n ? '\n' : ' ');
    return 0;
}