题解十三：P14028 【MX-X20-T2】「FAOI-R7」最小极差（jicha）

liu鲤鱼 · 2025-09-13 19:53:09 · 题解

题目。

思路

要使得极差最小，那就要让小的数尽可能变大，大的数尽可能变小。我们可以用 a_i 表示第 i 项的原值，b_i 表示第 i 项最大可以被修改几次。我们使用一个结构体来存储。

怎么处理 b_i 的值呢？最开始时我的想法是：每次读入 l 和 r，将 i \in [l,r] 中每个 b_i 增加 1。然后不出意外超时了两个点。所以就改成了使用差分的方式，成功通过。

for(ll i=1;i<=m;i++){
    cin>>l>>r;
    num[l].b++,num[r+1].b--;
}for(ll i=1;i<=n;i++)
    num[i].b+=num[i-1].b;

我们依据输入数组的大小从小到大对结构体排序，此时第 1 项的原值最大，第 n 项的原值最小。显然，对于每一项，该项最大值是 a_i+b_i，最小值是 a_i-b_i。那么，按照“小的数尽可能变大，大的数尽可能变小”的原则，使 a_1 \gets a_1+b_1，最大值 a_n \gets a_n-b_n，这时极差就是 a_n-a_1，结束了……吗？

事实上，这玩意连样例都过不去。因为此时新的 a_1 不一定是序列中最小的数，a_n 也不一定是最大的数。甚至可能出现 a_1 > a_n。

我们定义最小值 mi 和最大值 ma，然后遍历两次数组，一次更新 mi，一次更新 ma。

开始时，使 mi \gets a_1+b_1，然后对于每一个位置 i：

• 如果 mi > a_i，即 a_i 是序列中最小的，我们同样按照“小的数尽可能变大”的原则，获得一个 a_i+b_i，并将它同 mi 比较，取一个较小的值更新 mi；
• 反之，因为序列单调，后面就没有比它小的了，结束循坏。

  for(ll i=1;i<=n;i++){
  if(num[i].a<mi)
      mi=min(mi,num[i].a+num[i].b);
  else break;

对于 ma，操作相同，只不过遍历方向不同。

最后，输出答案 ma-mi 即可。别忘了特判 ma < mi 的情况（例如原序列全部相等）。

代码

//6.70s / 3.61MB / C++17 O2
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll t,n,m,l,r,mi,ma;
struct node{
    ll a,b;
}num[200010];
bool cmp(node x,node y){return x.a<y.a;}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(ll i=1;i<=n;i++){
            cin>>num[i].a;
            num[i].b=0;
        }for(ll i=1;i<=m;i++){
            cin>>l>>r;
            num[l].b++,num[r+1].b--;
        }for(ll i=1;i<=n;i++)
            num[i].b+=num[i-1].b;
        sort(num+1,num+n+1,cmp);
        mi=num[1].a+num[1].b;
        ma=num[n].a-num[n].b;
        for(ll i=1;i<=n;i++){
            if(num[i].a<mi)
                mi=min(mi,num[i].a+num[i].b);
            else break;
        }for(ll i=n;i>0;i--){
            if(num[i].a>ma)
                ma=max(ma,num[i].a-num[i].b);
            else break;
        }if(ma<mi) cout<<"0\n";
        else cout<<ma-mi<<"\n";
    }return 0;
}//喜欢就点个赞呗 QAQ