50 · 模拟赛二：150 分钟 5 题

维护一个下标队列 q，保证 q 里的下标递增、对应的 a 值也递增。此时队头 a[q[h]] 就是当前窗口的最小值。

每步三件事：① 新元素入队前，把队尾所有“值 ≥ 新元素”的下标弹掉——它们既不如新元素小、又比新元素先过期，永远没机会了；② 把 i 放进队尾；③ 检查队头是否还在窗口 [i−k+1, i] 里，不在就弹掉。

正确性：队列里值单调递增，所以队头是整个队列的最小值；队头一定在窗口内（过期就弹了）。被弹掉的下标要么值更大且更靠左，要么已经过期，都不可能成为任何后续窗口的答案。

复杂度：每个下标最多进队一次、出队一次，while 的总执行次数不超过 n，整体 O(n)。

最大值完全同构：把队尾弹出条件从 a[q[t]] ≥ a[i] 改成 a[q[t]] ≤ a[i]，别的一个字都不改。

输出细节：前 k−1 步窗口没填满，不输出；行末只换行，不加多余空格。

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

int n, k;
int a[1000005];
int q[1000005];                  // 手写双端队列，存的是下标

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

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // ---- 最小值：队列里的下标对应的 a 值严格递增，队头即窗口最小值 ----
    int h = 1, t = 0;                        // h > t 表示队列为空
    for (int i = 1; i <= n; ++i) {
        while (h <= t && a[q[t]] >= a[i]) --t;   // 队尾比新来的大：它这辈子都比不过新来的
        q[++t] = i;
        if (q[h] < i - k + 1) ++h;               // 队头已经滑出窗口左端
        if (i >= k) cout << a[q[h]] << (i == n ? '\n' : ' ');
    }

    // ---- 最大值：同一个骨架，只把比较方向反过来 ----
    h = 1; t = 0;
    for (int i = 1; i <= n; ++i) {
        while (h <= t && a[q[t]] <= a[i]) --t;
        q[++t] = i;
        if (q[h] < i - k + 1) ++h;
        if (i >= k) cout << a[q[h]] << (i == n ? '\n' : ' ');
    }
    return 0;
}

答案 = n − （能留下的最多人数）。所以问题变成“最多能留下几人”。

枚举顶峰 i。左边必须以 i 结尾且严格递增，长度就是 f[i] = 以 i 结尾的最长上升子序列；右边必须以 i 开头且严格递减，长度是 g[i] = 以 i 开头的最长下降子序列。

以 i 为顶峰时的最大保留人数 = f[i] + g[i] − 1，减 1 是因为顶峰自己被两段都算了一次。

f 从左往右推：f[i] = 1 + max{ f[j] : j < i 且 a[j] < a[i] }，没有合法的 j 时 f[i] = 1。

g 从右往左推，转移条件同样是 a[j] < a[i]：g[i] = 1 + max{ g[j] : j > i 且 a[j] < a[i] }。

两遍都是 O(n²)，总 O(n²) = 10⁴ 次操作。最后输出 n − max(f[i]+g[i]−1)。

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

int n, a[105];
int f[105], g[105];              // f：以 i 结尾的最长上升长度；g：以 i 开头的最长下降长度

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

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 左半边：以 i 结尾的最长上升子序列
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;                            // 至少包含自己
        for (int j = 1; j < i; ++j)
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);   // 严格递增：不能取等
    }

    // 右半边：以 i 开头的最长下降子序列，从右往左推
    for (int i = n; i >= 1; --i) {
        g[i] = 1;
        for (int j = i + 1; j <= n; ++j)
            if (a[j] < a[i]) g[i] = max(g[i], g[j] + 1);
    }

    int best = 0;                            // 能留下的最多人数
    for (int i = 1; i <= n; ++i)
        best = max(best, f[i] + g[i] - 1);   // 顶峰被算两次，减 1

    cout << n - best << "\n";                // 问的是出列人数，不是留下人数
    return 0;
}

二分答案 d：判定“最短跳跃距离 ≥ d”是否可行。d 越大越难满足，单调性成立。

check(d)：last 记录上一块“保留下来的落脚点”坐标（起点是 0），从左往右扫岩石。若 a[i] − last < d，这跳太短，只能把第 i 块搬走（cnt++），last 不变；否则保留它，last = a[i]。

扫完还要检查最后一跳 L − last：若它 < d，就把最后保留的那块石头搬走（不是搬终点），这样“上一落脚点 → L”的距离只会更大，一定也 ≥ d。

为什么贪心最优：能保留就保留，保留只会让后续的距离更容易够（last 更靠右）。提前搬走一块只会让跨度更大、消耗更多次数，不可能更优。

判定条件是 cnt ≤ M：不超过 M 块就合法，题目说的是“至多移走 M 块”。

二分区间 [1, L]：答案至少 1，至多 L（一块石头都不留时就是 L）。求最大可行值，中点要上取整。

复杂度 O(N log L) ≈ 5×10⁴ × 30 = 1.5×10⁶，稳过。

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

int L, n, m;
int a[50005];                    // a[1..n] 是岩石坐标；起点 0 由 last 的初值表示

// 判定：能不能只移走 ≤ m 块石头，使每一跳都 ≥ d
bool check(int d) {
    int cnt = 0, last = 0;               // last：上一个保留的落脚点
    for (int i = 1; i <= n; ++i) {
        if (a[i] - last < d) ++cnt;      // 这跳太短，只能搬走第 i 块
        else last = a[i];                // 跳得到，保留它
    }
    if (L - last < d) ++cnt;             // 最后一跳不够长：搬走 last 这块（不是终点）
    return cnt <= m;                     // “至多 m 块”，不是“恰好 m 块”
}

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

    cin >> L >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int lo = 1, hi = L;                  // 答案至少 1，至多 L
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;    // 上取整：求最大可行值必须这么写
        if (check(mid)) lo = mid;            // 可行，试着更大
        else hi = mid - 1;                   // 不可行，必须更小
    }
    cout << lo << "\n";
    return 0;
}

逆序对总数 = 对每个位置 i，统计“右边比 aᵢ 小的元素个数”，全部累加。

值域到 10⁹，桶开不下。先离散化：把 a 复制成 b，排序去重，用 lower_bound 把每个 aᵢ 换成排名，排名范围 1..sz，sz ≤ n ≤ 5×10⁵。

从右往左扫。树状数组 t 里记的是“某个排名已经出现过几次”。扫到 aᵢ 时，排名是 r，则 sum(r−1) 就是右边比它小的个数，直接加进答案；然后把 r 加进树状数组。

为什么用 r−1 而不是 r：逆序对要求严格大于，相等元素不能算。排名相同意味着值相等，必须排除。

正确性：每个逆序对 (i, j) 在扫描到 i 时被恰好数到一次——那时 j 已经进树状数组，且排名更小。

复杂度 O(n log n)：离散化 O(n log n)，每次查询和修改 O(log n)，总计约 5×10⁵ × 19 × 2 次操作。

答案上界：n(n−1)/2 ≈ 1.25×10¹¹，必须 long long。

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

int n;
int a[500005], b[500005];        // b 是排序去重用的副本
int t[500005];                   // 树状数组：t[i] 记录“排名 i 出现了几次”
int sz;                          // 排名上界 = 不同值的个数

int lowbit(int x) { return x & -x; }

void add(int i) {
    for (; i <= sz; i += lowbit(i)) ++t[i];
}

int sum(int i) {                 // 排名 ≤ i 的元素个数
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += t[i];
    return s;
}

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

    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; b[i] = a[i]; }

    // 离散化：排序 + 去重，把值换成排名
    sort(b + 1, b + n + 1);
    sz = unique(b + 1, b + n + 1) - (b + 1);

    long long ans = 0;                       // 逆序对最多 1.25×10¹¹，int 装不下
    for (int i = n; i >= 1; --i) {           // 从右往左，保证树状数组里只有 i 右边的数
        int r = lower_bound(b + 1, b + sz + 1, a[i]) - b;   // a[i] 的排名
        ans += sum(r - 1);                   // 右边严格小于 a[i] 的个数
        add(r);
    }

    cout << ans << "\n";
    return 0;
}

断环成链：把数组复制一份接在后面，得到 a[1..2n]。环上任意一种“从哪断开”的合并方案，都对应 2n 链上一个长度为 n 的连续区间。答案在这 n 个区间里取最优。

状态：f[i][j] = 把 a[i..j] 合并成一堆的最小得分；g[i][j] 同理求最大。

转移：最后一次合并必然把 a[i..k] 与 a[k+1..j] 两堆合成一堆，本次得分 = 这一段总和。f[i][j] = min over k∈[i, j−1] of f[i][k] + f[k+1][j] + (pre[j] − pre[i−1])。

顺序：按区间长度 len 从小到大枚举。长度 1 的区间不需要合并，得分 0。不能用“从 i 推到 j”的方式，因为 f[i][j] 依赖的所有子区间长度都比它短。

边界：f[i][i] = 0，其余 f 初值设成 INF；g 全部初值 0（最大值的下界就是 0）。

答案：对 i = 1..n 取 f[i][i+n−1] 的最小值、g[i][i+n−1] 的最大值。

复杂度 O(n³)：区间 O(n²) 个（实际是 2n 个起点 × n 种长度），每个枚举 O(n) 个分界点，n = 100 时约 2×10⁶ 次。

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

int n;
long long a[205], pre[205];
long long f[205][205], g[205][205];      // f：最小得分，g：最大得分

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

    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i + n] = a[i]; }   // 断环成链
    for (int i = 1; i <= 2 * n; ++i) pre[i] = pre[i - 1] + a[i];     // 前缀和，O(1) 取段和

    memset(f, 0x3f, sizeof(f));              // 求最小值：初值设成极大
    for (int i = 1; i <= 2 * n; ++i) f[i][i] = 0;   // 一堆不用合并，得分 0

    for (int len = 2; len <= n; ++len)                    // 区间长度，先短后长
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {      // 左端点
            int j = i + len - 1;
            long long s = pre[j] - pre[i - 1];            // 本次合并的得分
            for (int k = i; k < j; ++k) {                 // 最后一次合并的分界
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s);
                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s);
            }
        }

    long long mn = LLONG_MAX, mx = 0;
    for (int i = 1; i <= n; ++i) {                        // n 种断法
        mn = min(mn, f[i][i + n - 1]);
        mx = max(mx, g[i][i + n - 1]);
    }
    cout << mn << "\n" << mx << "\n";
    return 0;
}