自动搬运

查看原文

来自洛谷，原作者为

	Circle_Table Bye.

搬运于2025-08-24 23:12:43，当前版本为作者最后更新于2025-04-09 22:35:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目要求我们使超车次数最大，且任何车 $x$ 不应当超越另一辆车 $y$ 超过一次，并且要符合最终以输入的顺序抵达终点。

然后注意到第一组样例的后两行：为了使超车次数最大，这两辆车互相超了一次。再通过观察，可以得出两条结论。在 $i<j$ 的前提下：

• 当 $c_i>c_j$ 时，显然车 $i$ 被车 $j$ 超了一次。但如果车 $j$ 将车 $i$ 再超一次，由于车 $i$ 已经超过一次车 $j$ ，就超不回来了。因此这种情况下超车次数会增加一次。
• 当 $c_i<c_j$ 时，和样例一样，互相超一次。因此这种情况下超车次数会增加两次。

归纳一下：遇到逆序对，超车次数增加一次；遇到正序对，超车次数增加两次。到这里 $m$ 就已经可以求出来了。

至于后面的，由于最终情况下的最后一个车是不会再超了的，所以整个步骤就相当于从后向前进行冒泡排序，但是是从升序到要求的最终顺序。于是思路就出来了，从最后一个要被哪些车超过，慢慢往前排即可。

那么前面求出 $m$ 的过程也就为我们提供了思路，这里也就可以优化掉（事实上本质并没有改变）专门遍历求 $m$ 的过程。思路讲完了，代码如下。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int n,m;
int a[1145],p[1145],c[1145];//a指i上的数，p指数字i的位置，c指最终状态
int t,x;
vector<pair<int,int> >v;
//逆序对：超车一次
//正序对：超车了，但又被超回来了（使超车次数最大）
int main(){
	ios;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		a[i]=i;p[i]=i;
	}
//	for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){
//			m++;if(c[i]<c[j])m++;
//	} }cout<<m;
//	这一段可直接求出m，但是做完后发现其实不必
	for(int qwq=n;qwq>=1;qwq--){
		t=c[qwq];x=p[t];
		for(int i=x-1;i>=1;i--){
			v.push_back({t,a[i]});
			p[t]=i;
			p[a[i]]=i+1;
			a[i+1]=a[i];
			a[i]=t;
		}
		for(int i=2;i<=qwq;i++){
			v.push_back({a[i],t});
			p[t]=i;
			p[a[i]]=i-1;
			a[i-1]=a[i];
			a[i]=t;
		}
	}m=v.size();
	cout<<m<<'\n';
	for(int i=0;i<m;i++)
		cout<<v[i].first<<' '<<v[i].second<<'\n';
	return 0;
}

感谢阅读！