首页 > 代码库 > 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【构造】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。