专栏文章

题解：P14062 【MX-X21-T7】[IAMOI R5] 若我不曾见过太阳

TTTC_84
P14062题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@min147lh
此快照首次捕获于
2025/12/01 18:51
3 个月前
此快照最后确认于
2025/12/01 18:51
3 个月前
查看原文

若我不曾见过太阳题解

这是一篇知更鸟推人的题解。
因为知更鸟，所以切了这道题，我的博客还有知更鸟赛的其他题解，欢迎来玩！
是一道思维好题呢。
首先，我们读懂题意后，通过手模样例发现排序与同剩余系相邻数之间的距离有关。
具体的说：对于下标为 ii 和 jj 的数，若 i≡j(modk)i \equiv j \pmod k 则 ii 和 jj 会在第 kk 级排序中被交换。
发现到这里，我们距离答案就不远了，考虑交换两个数的意义是将一对逆序对恢复正序，自然的想到，当 ii 和 jj 是距离最小的逆序对时，将他们交换完成，整个数列必然有序。所以最后一次排序的级数一定是 min⁡i>j,ai<aj∣j−i∣\min_{i>j,a_i < a_j} |j-i|，即距离最小的逆序对。答案即为 n−kn-k。
考虑维护这个式子，关键在于这个数列是排列。
发现对于一个数 xx，它有序后一定在下标为 xx 的位置，这时候，在下标 xx 之前且数值上大于 axa_x 的数和在下标 xx 之后且数值上小于等于 axa_x 的数构成逆序对，在下标 xx 之前的最后一个满足条件的数和在下标 xx 之后最后一个满足条件的数就是对于 xx 的距离最小的逆序对，维护这个自然的想到单调栈。
最后，知更鸟可爱捏～
代码：
CPP
#include<bits/stdc++.h>
#define Robin 0
using namespace std;
const int N=4e6+10;
int st[N],top;
int a[N];
int len[N];
int n;

void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	top=0;
	int ans=INT_MAX;
	for(int i=1;i<=n;i++)
	{
		st[++top]=i;
		while(top && a[st[top]]<=i) top--;
		if(top) len[i]=st[top];
		else len[i]=0;
	}

	top=0;
	for(int i=n;i>=1;i--)
	{
		while(top && a[st[top]]>i) top--;
		if(top) len[i]=st[top]-len[i];
		if(len[i]>0) ans=min(ans,len[i]);
		st[++top]=i;
	}
	if(ans==INT_MAX) cout<<"0\n";
	else cout<<n-ans<<'\n';
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	// freopen("text.in","r",stdin);
	// freopen("text.out","w",stdout);
	int T;
	cin>>T;
	while(T--) solve();
	return Robin;
}

评论

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

正在加载评论...