题解：CF2081B Balancing

bsdsdb · 2025-03-18 16:52:50 · 题解

题意：\{a_i\}_{i=1}^n，不存在 a_i=a_{i+1}。一次操作可以选择 l,r，自主决定一个整数序列 \{{a'}_i\}_{i=l}^r，满足 \forall i\in[l,r):\gdef\sgn{\operatorname{sgn}}\sgn({a'}_{i+1}-{a'}_i)=\sgn(a_{i+1})-\sgn(a_i)，然后用 {a'}_{[l,r]} 替换 a_{[l,r]} 问最少多少次操作可以把 a 变成严格单调递增。

称「下降数 d」为 [a_i>a_{i+1}] 的数量。感觉结论不是很好想啊，思路也不好表述，就多造几个样例就出来了。

引理 1：d=0 时答案为 0。

显然。

引理 2：一次操作最多将 d 减少 2。

操作 (l,r) 只有可能删掉 l-1,r 两个下降点。

推论 1：答案的下界为 \left\lceil\frac d2\right\rceil。

引理 3：当 d\ge 3 时，一次操作可以将 d 减少 2。

如图：

引理 4：如果每次操作都让 d 减少 2，那么最左边的へ的拐点处高度动不了。右边同理。

如果想让他动，因为他是最左边的，再左边没有下降点了，d 也就减不了 2 了。

引理 5：当 d=1 时答案上界为 1。

如图：

推论 2：d=1 时答案为 1。

推论 3：2\nmid d 时答案为 \left\lceil\frac d2\right\rceil。

引理 6：当 d=2，有 l\neq r-1,a_{l}\ge a_{l+1},a_{r-1}\ge a_r 时，答案上界为 1。

如图：

推论 4：此时答案为 1。

推论 5：2\mid d,a_{l}\ge a_{l+1},a_{r-1}\ge a_r，l 是最左边下降点，r 是最右边下降点往右一个（就是图中加粗的右边的黑点）时，答案为 \frac d2。

引理 7：当 d=2 但不符合引理 6 中所述其他条件时，答案为 2。

里面全是上升，最理想情况压到全 +1。此时左右两点平均斜率至少为 1，矛盾，因此一次操作压不进去。

两次操作很简单，左边点一按，右边点一抬就 ok 了。

引理 8：符合引理 7 所述情况但 2\mid d,d>2 时答案下界为 \frac d2+1。

等价于 \frac d2 是不行的。如果一直按引理 2 的方法调整，那么根据引理 4，最后肯定面临一个引理 7 的情况。

推论 6：此情况下答案为 \frac d2+1。

结合引理 1，推论 3，推论 5，推论 6 可得出答案。

#include <bits/stdc++.h>
using namespace std; 
namespace heead {
    // types
    using i32 = int32_t;
    using i64 = int64_t;
    using i128 = __int128;
    using f32 = float;
    using f64 = double;
    using f128 = __float128;
    using ll = long long;
    using ldb = long double;
    #define umap unordered_map
    #define uset unordered_set
    #define prque priority_queue
    #define pi32 pair<i32, i32>
    #define pi64 pair<i64, i64>
    #define pll pair<ll, ll>
    // functions
    #define emp emplace
    #define empb emplace_back
    #define empf emplace_front
    #define mkp make_pair
    mt19937_64 rd(chrono::high_resolution_clock().now().time_since_epoch().count());
    // constants
    #define csep constexpr
    csep i64 inf = 0x3f3f3f3f3f3f3f3fll;
    csep f64 eps = 1e-7;
    csep f64 PI = 3.14159265358979323846264338327950288419716939937510582097;
    // non-std type io
    istream& operator>>(istream& in, i128& x) {
        string input;
        in >> input;
        x = 0;
        for (char c : input) {
            if (c == '-') {
                continue;
            }
            x = (x << 3) + (x << 1) + (c & 15);
        }
        if (input[0] == '-') {
            x *= -1;
        }
        return in;
    }
    ostream& operator<<(ostream& out, i128 x) {
        stack<char> output;
        if (x < 0) {
            out << '-';
            x *= -1;
        }
        if (!x) {
            out << '0';
            return out;
        }
        while (x) {
            output.emp((x % 10) | 48);
            x /= 10;
        }
        while (!output.empty()) {
            out << output.top();
            output.pop();
        }
        return out;
    }
    istream& operator>>(istream& in, f128& x) {
        string input;
        in >> input;
        f128 mul = 1;
        i64 id = (input.find('.') == string::npos ? input.length() : input.find('.')) - (input[0] == '-') - 1;
        for (ll i = 1; i <= id; ++i) {
            mul *= 10;
        }
        x = 0;
        for (char c : input) {
            if (c == '.' || c == '-') {
                continue;
            }
            x += mul * (c & 15);
            mul /= 10;
        }
        if (input[0] == '-') {
            x *= -1;
        }
        return in;
    }
    csep i64 F128ACC = 12;
    ostream& operator<<(ostream& out, f128 x) {
        // negative case
        if (x < 0) {
            out << '-';
            x *= -1;
        }
        // integer part
        out << i128(x);
        x -= i128(x);
        // fractional part
        for (ll i = 1; i <= F128ACC; ++i) {
            x *= 10;
        }
        if (!x) {
            return out;
        }
        out << '.';
        // prefix 0
        i128 y = x;
        i128 _y = y;
        for (ll i = 1; i <= F128ACC; ++i) {
            if (!_y) {
                out << '0';
            }
            _y /= 10;
        }
        // suffix 0
        while (y && y % 10 == 0) {
            y /= 10;
        }
        // out
        out << i128(y);
        return out;
    }
}
using namespace heead;

ll n, a[1000005];
vector<pll> inv;

void init() {
    fill_n(a, n + 4, inf);
    inv.clear();
}
int mian() {
    cin >> n;
    a[n + 1] = inf;
    for (ll i = 1; i <= n; ++i) cin >> a[i];
    ll l = 1, ans = 0;
    for (ll i = 2; i <= n; ++i) {
        if (a[i - 1] > a[i]) {
            inv.empb(mkp(i - 1, i));
        }
    }
    if (inv.size() <= 1) {
        cout << inv.size() << endl;
        return 0;
    }
    if (inv.size() % 2) {
        cout << inv.size() / 2 + 1 << endl;
    } else {
        if (inv.back().second - inv[0].first <= a[inv.back().second] - a[inv[0].first]) {
            cout << inv.size() / 2 << endl;
        } else {
            cout << inv.size() / 2 + 1 << endl;
        }
    }
    return 0;
}

#define FASTIO
int main() {
    #ifdef FASTIO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #endif
    i32 T;
    cin >> T;
    while (T--) init(), mian(), init();
    return 0;
}