题解归档 - cf362C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf362C
• 本地来源：problems/cf362C/idea.md
• 题目链接：https://codeforces.com/contest/362/problem/C
• 原始标题：CF362C Insertion Sort

思路

CF362C Insertion Sort

题意

给定 0..n-1 的排列，先恰好交换一次两个位置，再对数组做插入排序（相邻 swap 实现），统计 swap 调用次数。求最小次数及达到最小值的交换对 (i,j) 个数（i<j）。

插入排序的 swap 次数 = 逆序对数。

做法

1. 预处理总逆序对 cur（O(n²)）。
2. 预处理 f[j][i] = 前缀 [1,j] 中值 < a[i] 的个数；g[j][i] = 前缀中值 > a[i] 的个数。
3. 枚举交换 l<r，交换后逆序对变化量 O(1)：

t = cur + (g[r][l]-g[l][l]) - (f[r][l]-f[l][l]) + (f[r][r]-f[l][r]) - (g[r][r]-g[l][r])

含义：区间 [l,r] 内，与 a[l]、a[r] 相关的逆序对增减四项。

4. 取最小 t，统计方案数。

复杂度 O(n²)，内存两个 int[n][n]（约 200MB，在 256MB 限制内）。

样例

• [4,0,3,1,2]：最优 3 次，方案 (0,3),(0,4) 共 2 个。
• [1,2,3,4,0]：最优 3 次，与最后一个位置交换共 4 个。

结论

AC 目标文件：solution.cpp。题面保证存在一次交换使 swap 次数下降，故初始逆序对 > 0。

代码

来源：problems/cf362C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 06:58:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=5005;
ll s[maxn],n,i,j,l,r,cur,ans,cnt,pd;
int f[maxn][maxn],g[maxn][maxn];
int main(){
    cin>>n;
    for(i=1;i<=n;i++) cin>>s[i];
    cur=0;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            if(s[i]>s[j]) cur++;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            f[j][i]=f[j-1][i]+(s[j]<s[i]);
            g[j][i]=g[j-1][i]+(s[j]>s[i]);
        }
    }
    ans=cur;
    cnt=0;
    for(l=1;l<n;l++){
        for(r=l+1;r<=n;r++){
            pd=cur+(g[r][l]-g[l][l])-(f[r][l]-f[l][l])+(f[r][r]-f[l][r])-(g[r][r]-g[l][r]);
            if(pd<ans){
                ans=pd;
                cnt=1;
            }else if(pd==ans) cnt++;
        }
    }
    cout<<ans<<" "<<cnt<<"\n";
    return 0;
}