首页 > 代码库 > Codeforces 362C. Insertion Sort【构造】

Codeforces 362C. Insertion Sort【构造】

题目大意:

给出一个排列,问交换某两个数之后,该排列的逆序数最小为多少,并找出可以交换多少对数能够得到这样的逆序数。

做法:

由于数据范围只有5000,那么直接暴力O(n^2)也是可行的,既然如此,我们暴力枚举两个交换的元素的下标,思考一下交换之后,整个序列的逆序数会怎么改变。假设我们交换的是a[i],a[j](由于需要得到的是逆序数最小,那么交换的两个数满足,a[i]>a[j]),如么逆序数一定和两个元素之间分别大于,小于两个数的个数有关。那么我们假设mi[i][j]表示在a[0]~a[j]之间有多少个数小于a[i],ma[i][j]表示在a[0]~a[j]之间有多少个数大于a[i],cur表示原序列的逆序数。那么交换两个数之后,新序列的逆序数与原先的逆序数cur存在如下关系:
new=cur+mi[j][j-1]-mi[j][i]+ma[i][j-1]-ma[i][i]-(ma[j][j-1]-ma[j][i]+mi[i][j-1]-mi[i][i])-1

这样的话,得记录两个数组,但其实容易发现,mi[i][j]和ma[i][j]是存在关系的,ma[i][j]=j+1-mi[i][j],这样的话,可以减少一个数组的开支。
变换之后的表达式如下:
new=cur+2*(mi[j][j-1]-mi[j][i]-mi[i][j-1]+mi[i][i])-1

代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#define N 5005
using namespace std;
int mi[N][N],ma[N][N],num[N],cnt,ans=INT_MAX;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&num[i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(num[j]>num[i]) ma[i][j]=1;
            if(num[j]<num[i]) mi[i][j]=1;
            if(j) ma[i][j]+=ma[i][j-1],mi[i][j]+=mi[i][j-1];
        }
    int cur=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(i<j&&num[i]>num[j]) cur++;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            if(num[i]<num[j]) continue;
            int temp=cur;
            temp+=(mi[j][j-1]-mi[j][i]+ma[i][j-1]-ma[i][i]);
            temp-=(ma[j][j-1]-ma[j][i]+mi[i][j-1]-mi[i][i]);
            temp--;
            if(ans==temp) cnt++;
            else if(ans>temp) ans=temp,cnt=1;
        }
    cout<<ans<<" "<<cnt<<endl;
    return 0;
}


Codeforces 362C. Insertion Sort【构造】