题解：P12092 [NERC2024] Adrenaline Rush

Circle_Table · 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;
}

感谢阅读！