专栏文章

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

lliu鲤鱼
P14028题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwwntq
此快照首次捕获于
2025/12/02 09:41
3 个月前
此快照最后确认于
2025/12/02 09:41
3 个月前
查看原文
题目。

思路

要使得极差最小，那就要让小的数尽可能变大，大的数尽可能变小。我们可以用 aia_i 表示第 ii 项的原值，bib_i 表示第 ii 项最大可以被修改几次。我们使用一个结构体来存储。
怎么处理 bib_i 的值呢？最开始时我的想法是：每次读入 ll 和 rr，将 i∈[l,r]i \in [l,r] 中每个 bib_i 增加 11。然后不出意外超时了两个点。所以就改成了使用差分的方式，成功通过。
CPP
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;
我们依据输入数组的大小从小到大对结构体排序，此时第 11 项的原值最大，第 nn 项的原值最小。显然，对于每一项，该项最大值是 ai+bia_i+b_i，最小值是 ai−bia_i-b_i。那么，按照“小的数尽可能变大，大的数尽可能变小”的原则，使 a1←a1+b1a_1 \gets a_1+b_1，最大值 an←an−bna_n \gets a_n-b_n，这时极差就是 an−a1a_n-a_1，结束了……吗？
事实上，这玩意连样例都过不去。因为此时新的 a1a_1 不一定是序列中最小的数，ana_n 也不一定是最大的数。甚至可能出现 a1>ana_1 > a_n。
我们定义最小值 mimi 和最大值 mama，然后遍历两次数组，一次更新 mimi，一次更新 mama。
开始时，使 mi←a1+b1mi \gets a_1+b_1，然后对于每一个位置 ii：
  • 如果 mi>aimi > a_i，即 aia_i 是序列中最小的，我们同样按照“小的数尽可能变大”的原则，获得一个 ai+bia_i+b_i，并将它同 mimi 比较，取一个较小的值更新 mimi；
  • 反之，因为序列单调，后面就没有比它小的了，结束循坏。
CPP
for(ll i=1;i<=n;i++){
	if(num[i].a<mi)
		mi=min(mi,num[i].a+num[i].b);
	else break;
对于 mama，操作相同，只不过遍历方向不同。
最后，输出答案 ma−mima-mi 即可。别忘了特判 ma<mima < mi 的情况（例如原序列全部相等）。

代码

CPP
//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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...