洛谷 P1873 [COCI 2011/2012 #5] EKO / 砍树

// P1873 的第 ① 版：从最高的那棵树一路往下试
//
// f(H) 随 H 增大而减小，所以从 H = max(h) 往下走，**第一个**让 f(H) >= M 的 H 就是答案。
// 想法完全正确，一行都不用怀疑。
//
// ⚠ 它的代价是 O(max(h) × N)：满数据 4×10⁵ × 10⁶ = **4×10¹¹**，没有任何机会。
//   而且注意，慢的来源是「**答案的取值范围**」而不是「输入规模」——
//   哪怕 N 只有 10，只要树高到 4×10⁵，它照样要试四十万次。
//
// ★ 这是「二分答案」这类题的标志性形状：**暴力枚举的是答案，而答案的范围很大**。
//   ⇒ 一旦发现「换成更大的答案只会更难满足」，就该想到二分。

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

static int h[1000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    int hi = 0;
    for (int i = 0; i < n; i++) { cin >> h[i]; hi = max(hi, h[i]); }

    for (int H = hi; H >= 0; H--) {
        long long s = 0;
        for (int i = 0; i < n; i++) if (h[i] > H) s += h[i] - H;
        if (s >= m) { cout << H << '\n'; return 0; }
    }
    cout << 0 << '\n';
    return 0;
}

// P1873 EKO / 砍树 —— 能 AC 的那一版：二分答案
//
// 设 f(H) = 锯片高 H 时能得到的木材 = Σ max(h_i − H, 0)。
// H 越高，f(H) 越小（**单调不增**）—— 要的是**最大**的 H 使 f(H) >= M。
//
// ★ 这就是「二分答案」：答案本身在一条数轴上，而「这个答案行不行」是单调的。
//   H 的范围是 [0, max(h)]，一共 log2(4×10⁵) ≈ 19 次判定，每次 O(N)。
//
// ⚠ 三个边界，各值一条测试点：
//   ① 下界必须是 **0** 不是 1 —— 树很矮的时候答案真的可能是 0（见 p1873Lo.cpp）；
//   ② 判定要写 **f(mid) >= M** 不是 > M —— 「至少 M 米」是可以正好等于的（见 p1873Gt.cpp）；
//   ③ sum 必须是 **long long**：N = 10⁶、h_i <= 4×10⁵ ⇒ 总和最大 4×10¹¹（见 p1873Int.cpp）。
//
// ★ M 本身呢？M <= 2×10⁹ 而 int 上限 2 147 483 647 —— **装得下，但余量只有 7%**。
//   （这笔账见 p1873Count.cpp。用 long long 读它更省心，这里就是这么做的。）

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

static int h[1000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    int hi = 0;
    for (int i = 0; i < n; i++) { cin >> h[i]; hi = max(hi, h[i]); }

    auto f = [&](int H) {                       // 高度 H 时能得到多少木材
        long long s = 0;
        for (int i = 0; i < n; i++) if (h[i] > H) s += h[i] - H;
        return s;
    };

    int lo = 0, hiB = hi, ans = 0;              // ① 下界是 0
    while (lo <= hiB) {
        int mid = lo + (hiB - lo) / 2;
        if (f(mid) >= m) { ans = mid; lo = mid + 1; }   // ② >= 不是 >
        else hiB = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}

// P1873 的第 ③ 版：排序 + 后缀和，**一次二分都不做**
//
// 把树高排好序（升序）。对给定的 H，设有 k 棵树不高于 H，那么
//
//        f(H) = (后 n−k 棵的高度和) − (n − k) × H
//
// 在「恰好有 k 棵树不高于 H」的那一段 H 里，f 是一条直线。
// 于是对每个 k 直接解出「这一段里最大的、还能满足 f(H) >= M 的 H」：
//
//        H = (suf[k] − M) / (n − k)        （向下取整，再夹回这一段的范围里）
//
// 取所有 k 里最大的那个 H 就是答案。排序 O(N log N)，之后只扫一趟。
//
// ★★ 这一版是这一页回答「双指针能不能用」的地方：
//   **排完序之后确实有一个指针在单调地走** —— 就是那个 k（被锯到的树的数量）。
//   H 越大，被锯到的树越少，k 单调不减。
//   ⇒ 「双指针」的那点直觉没有白费，只是它作用在**排好序的高度轴**上，
//     而不是题面给的那排树上。区别在正文第 3 步。

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

static int h[1000006];
static long long suf[1000007];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n);

    suf[n] = 0;
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + h[i];

    long long ans = 0;
    for (int k = 0; k < n; k++) {               // 前 k 棵不高于 H，后 n−k 棵被锯
        long long cntCut = n - k;
        long long H = (suf[k] - m) / cntCut;    // 这一段里最大的可行 H
        if (H < 0) continue;
        long long loH = (k == 0) ? 0 : h[k - 1];        // 这一段 H 的下界
        long long hiH = h[k] - 1;                       // 上界（再高就轮到第 k 棵了）
        if (H > hiH) H = hiH;
        if (H < loH) continue;
        ans = max(ans, H);
    }
    cout << ans << '\n';
    return 0;
}

// 换一把尺子 + 两笔溢出账
//
// 用法：./p1873Count <n> <maxh>        人话版（带秒表）
//       ./p1873Count <n> <maxh> csv    只打 `键,值`，给 check:viz 用
//
// ① 尺子：这道题的暴力枚举的是**答案**，所以它的次数由**答案的取值范围**决定，
//    和 N 只是相乘的关系：枚举要算 maxh+1 次 f()，二分只要 ⌊log2(maxh)⌋+1 次。
//    ⇒ 满数据 4×10⁵ 次 vs 19 次，**差两万倍**。
//
// ② 溢出账之一（**木材总量**）：N × maxh = 4×10¹¹，int 差 186 倍 ⇒ 必须 long long。
// ③ 溢出账之二（**M 本身**）：题面 M <= 2×10⁹，int 上限 2 147 483 647 ——
//    **装得下，余量只有 7%**。⇒ 能用 int 读，但没什么道理省这一下。

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

static double now_ms() {
    timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1000.0 + t.tv_nsec / 1e6;
}

int main(int argc, char** argv) {
    long long n = (argc > 1) ? atoll(argv[1]) : 1000000;
    long long maxh = (argc > 2) ? atoll(argv[2]) : 400000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");

    long long intMax = 2147483647LL;
    long long steps = 0;
    for (long long x = maxh; x >= 1; x >>= 1) steps++;      // ⌊log2(maxh)⌋ + 1
    long long bruteCalls = maxh + 1;
    long long bruteOps = bruteCalls * n;
    long long binOps = steps * n;

    long long woodMax = n * maxh;
    long long mMax = 2000000000LL;

    /* 秒表：造一份顶格数据，二分 vs 排序 + 后缀和 */
    mt19937 rng(20260827u);
    vector<int> h((size_t)n);
    long long total = 0;
    for (long long i = 0; i < n; i++) { h[i] = 1 + (int)(rng() % (unsigned)maxh); total += h[i]; }
    long long m = total / 2;

    double t0 = now_ms();
    long long ansBin = 0;
    {
        int lo = 0, hiB = (int)maxh;
        while (lo <= hiB) {
            int mid = lo + (hiB - lo) / 2;
            long long s = 0;
            for (long long i = 0; i < n; i++) if (h[i] > mid) s += h[i] - mid;
            if (s >= m) { ansBin = mid; lo = mid + 1; } else hiB = mid - 1;
        }
    }
    double tBin = now_ms() - t0;

    t0 = now_ms();
    long long ansSort = 0;
    {
        vector<int> g = h;
        sort(g.begin(), g.end());
        vector<long long> suf((size_t)n + 1, 0);
        for (long long i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + g[i];
        for (long long k = 0; k < n; k++) {
            long long cut = n - k;
            long long H = (suf[k] - m) / cut;
            if (H < 0) continue;
            long long loH = (k == 0) ? 0 : g[k - 1];
            long long hiH = (long long)g[k] - 1;
            if (H > hiH) H = hiH;
            if (H < loH) continue;
            ansSort = max(ansSort, H);
        }
    }
    double tSort = now_ms() - t0;

    if (csv) {
        printf("n,%lld\nmaxh,%lld\nbruteCalls,%lld\nbinCalls,%lld\ncallRatio,%lld\n"
               "bruteOps,%lld\nbinOps,%lld\n"
               "woodMax,%lld\nwoodFitsInt,%d\nwoodOverInt,%lld\n"
               "mMax,%lld\nmFitsInt,%d\nmHeadroomPct,%lld\n"
               "same,%d\n",
               n, maxh, bruteCalls, steps, bruteCalls / steps, bruteOps, binOps,
               woodMax, woodMax <= intMax ? 1 : 0, woodMax / intMax,
               mMax, mMax <= intMax ? 1 : 0, (intMax - mMax) * 100 / mMax,
               ansBin == ansSort ? 1 : 0);
    } else {
        printf("n = %lld, 树高上限 = %lld\n\n", n, maxh);
        printf("(1) 从高往低枚举   %10lld 次 f()   => %lld 次加法\n", bruteCalls, bruteOps);
        printf("(2) 二分答案       %10lld 次 f()   => %lld 次加法\n", steps, binOps);
        printf("=> 差 %lld 倍\n\n", bruteCalls / steps);
        printf("木材总量的上界 n x maxh = %lld，int 上限 %lld => %s（差 %lld 倍）\n",
               woodMax, intMax, woodMax <= intMax ? "装得下" : "装不下", woodMax / intMax);
        printf("M 的上界        %lld，int 上限 %lld => %s（余量 %lld%%）\n\n",
               mMax, intMax, mMax <= intMax ? "装得下" : "装不下", (intMax - mMax) * 100 / mMax);
        printf("顶格数据上的秒表（答案 %lld）：\n", ansBin);
        printf("  二分答案         %8.1f ms\n", tBin);
        printf("  排序 + 后缀和    %8.1f ms\n", tSort);
        printf("\n两版答案%s\n", ansBin == ansSort ? "一致" : "不一致！");
    }
    return 0;
}

// 演示错误写法：判定写成 f(mid) > M，而题目要的是「**至少** M 米」
//
// 差一个等号。f(H) 正好等于 M 的时候，这一版判它「不行」，于是答案比正确答案小。
//
// ★ 这个 bug 明得很：**两组样例都抓得到**（样例 1 的答案 15 对应 f = 7 = M，
//   样例 2 的答案 36 对应 f = 20 = M）—— 出题人是故意的。
//   ⇒ 和 p1873Lo.cpp 正好凑一对：一个样例就挂，一个样例上完全正确。

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

static int h[1000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    int hi = 0;
    for (int i = 0; i < n; i++) { cin >> h[i]; hi = max(hi, h[i]); }

    auto f = [&](int H) {
        long long s = 0;
        for (int i = 0; i < n; i++) if (h[i] > H) s += h[i] - H;
        return s;
    };

    int lo = 0, hiB = hi, ans = 0;
    while (lo <= hiB) {
        int mid = lo + (hiB - lo) / 2;
        if (f(mid) > m) { ans = mid; lo = mid + 1; }     // ← 少了一个等号
        else hiB = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}

// 演示错误写法：二分的下界从 1 开始 —— 于是永远输出不了 0
//
// 答案真的可能是 0：树都很矮、M 又贴着总和的时候，锯片抬到 1 米就已经不够了。
// 例如 3 棵 1 米的树、M = 2：f(0) = 3 >= 2，f(1) = 0 < 2 ⇒ 答案是 **0**。
//
// ★ 这个 bug 暗得很：**两组样例都抓不到**，随机数据也几乎抓不到 ——
//   要「总高度只比 M 大一点点，而且树矮到抬一米就没了」才露头。
//   ⇒ 对拍档位 1 就是专门造这种数据的。

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

static int h[1000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    int hi = 0;
    for (int i = 0; i < n; i++) { cin >> h[i]; hi = max(hi, h[i]); }

    auto f = [&](int H) {
        long long s = 0;
        for (int i = 0; i < n; i++) if (h[i] > H) s += h[i] - H;
        return s;
    };

    int lo = 1, hiB = hi, ans = 1;              // ← 下界写成了 1，ans 也从 1 起
    while (lo <= hiB) {
        int mid = lo + (hiB - lo) / 2;
        if (f(mid) >= m) { ans = mid; lo = mid + 1; }
        else hiB = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}

// 数据生成器（P1873 对拍用）：`./p1873Gen <seed> [level]`
//
//   level 0（默认）随机：n <= 8、树高 <= 20、M 随机取在 (0, 总和) 里
//   level 1        **逼答案变成 0**：树全都很矮（1~3 米），M 贴着总和 ——
//                  锯片抬到 1 米就已经不够了
//   level 2        **让 f(H) 正好等于 M**：先随机一批树和一个 H，再令 M = f(H)
//
// ★ 三个档位各盯一个错版：
//   level 1 抓 p1873Lo（二分下界写成 1，永远输出不了 0）；
//   level 2 抓 p1873Gt（判定写成 > 而不是 >=）；
//   level 0 兜底。
//
// ⚠ 题面保证「所有树的高度总和 > M」，所以三个档位都得自己守住这一条 ——
//   否则造出来的是**无解**的数据，两个程序会「一致地输出垃圾」，看着全绿其实什么都没验。

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

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);

    int n = ri(1, 8);
    vector<int> h(n);
    long long total = 0, m = 1;

    if (level == 1) {
        do {
            for (int i = 0; i < n; i++) h[i] = ri(1, 3);
            total = accumulate(h.begin(), h.end(), 0LL);
            long long f1 = 0;
            for (int x : h) if (x > 1) f1 += x - 1;
            if (f1 + 1 <= total - 1) { m = ri((int)f1 + 1, (int)total - 1); break; }
            n = ri(2, 8); h.assign(n, 0);
        } while (true);
    } else if (level == 2) {
        do {
            for (int i = 0; i < n; i++) h[i] = ri(1, 20);
            total = accumulate(h.begin(), h.end(), 0LL);
            int H = ri(0, 20);
            long long f = 0;
            for (int x : h) if (x > H) f += x - H;
            if (f >= 1 && f < total) { m = f; break; }      // M = f(H)，且守住 total > M
            n = ri(1, 8); h.assign(n, 0);
        } while (true);
    } else {
        do {
            for (int i = 0; i < n; i++) h[i] = ri(1, 20);
            total = accumulate(h.begin(), h.end(), 0LL);
        } while (total < 2);
        m = ri(1, (int)total - 1);
    }
    printf("%d %lld\n", (int)h.size(), m);
    for (size_t i = 0; i < h.size(); i++) printf("%d%c", h[i], i + 1 == h.size() ? '\n' : ' ');
    return 0;
}

// 大数据生成器（P1873 计时 / 溢出用）：`./p1873GenBig [n] [maxh] [level]`
//
//   level 0（默认）随机树高 ∈ [1, maxh]，M 取总和的一半
//   level 1        **全都顶格**：每棵树都是 maxh 米，M 取总和的一半
//                  ⇒ 木材总量 4×10¹¹，int 版当场翻车
//
// ★ 这两档要的不是「更慢」，是**把那个溢出的门槛跨过去**：
//   int 只到 2.1×10⁹，而这里的木材总量是它的 186 倍。
//   小数据（几棵树、高度几十）离这条线差七八个数量级 —— 对拍**算术上**抓不到。

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

static mt19937 rng;

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 1000000;
    int maxh = (argc > 2) ? atoi(argv[2]) : 400000;
    int level = (argc > 3) ? atoi(argv[3]) : 0;
    rng.seed(12345);
    vector<int> h(n);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        h[i] = (level == 1) ? maxh : (1 + (int)(rng() % (unsigned)maxh));
        total += h[i];
    }
    printf("%d %lld\n", n, total / 2);
    for (int i = 0; i < n; i++) printf("%d%c", h[i], i == n - 1 ? '\n' : ' ');
    return 0;
}