题解：P10991 [蓝桥杯 2023 国 Python A] 选段排序

cf_x · 2025-08-14 16:47:55 · 题解

题目大意

给出三个正整数 n，p，q 和序列 A_i，选择一个区间进行排序，求区间排序后 A_q-A_p 最大可以是多少。

核心思路

首先我们知道对于区间 [L,R]，只要区间没有包含 p, q，那么这种排序是无意义的。

因为我们想要让 A_q-A_p 最大，所以我们有两种方式。

• 让 A_p 尽量小。
• 让 A_q 尽量大。

我们先解决让 A_p 尽量小的问题。我们发现对 [p,r],r\in[p,n] 排序是最优的。为什么呢？

• 当最小值的下标在 [p,n] 之间时，如果你排的是 [p-1,n]，那么最小值就跑到了 p-1 的位置上，那么答案会变小。所以不是最优的。
• 当最小值的下标在 [1,p-1] 之间时，这个最小值只会在排序区间的最左边，而不能来到 p 的位置上（提示：最小值的下标在 [1,p-1] 之间哦）。

同理，让 A_p 尽量大的问题也是一样的思路。

非核心思路

当我们排 [p, q+1] 时。这时，不应该是找最大值，而是次大的，因为最大值在 q+1 上。

其余同理。

代码

最后代码如下：

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

const int N = 2e5+10;

int n, p, q;
int a[N];
multiset<int, greater<int> > st1; // 可能有重复元素
multiset<int> st2;

signed main() {
    cin >> n >> p >> q;
    for (int i = 1;i<= n;i++) {
        cin >> a[i];
    }
    int ans = a[q]-a[p]; 
    int minn = 2e9;
    for (int i = p;i<= q;i++) {
        minn = min(minn, a[i]);
        st1.insert(a[i]);
        if (i == q) continue;
        ans = max(ans, a[q]-minn);
    } ans = max(ans, (*st1.begin()) - minn);
    int now = *st1.begin();
    for (int i = q+1;i<= n;i++) {
        minn = min(minn, a[i]);
        if (a[i] >= now) {
            ;
        } else {
            st1.insert(a[i]);
            st1.erase(st1.begin());
            now = *st1.begin();
        }
        ans = max(ans, now - minn);
    }
    int maxn = 0;
    for (int i = q;i>= p;i--) {
        maxn = max(maxn, a[i]);
        st2.insert(a[i]);
        if (i == p) continue;
        ans = max(ans, maxn-a[p]);
    } now = *st2.begin();
    ans = max(ans, maxn-now);
    for (int i = p-1;i>= 1;i--) {
        maxn = max(maxn, a[i]);
        if (a[i] <= now) {
        } else {
            st2.insert(a[i]);
            st2.erase(st2.begin());
            now = *st2.begin();
        }
        ans = max(ans, maxn-now);
    }
    cout << ans << endl;
    return 0;
}