本文主要是介绍FZOJ 2166 inversion，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算是一道模拟题吧，，，此题就逆序数不用归并排序之类的，而是用双层for循环模拟求解，，因为题意中要求任意两个数交换位置，所以只需在双层for循环中模拟两个数交换即可，在模拟的过程中，不需要准确的求出模拟之后的逆序数，只需要考虑逆序数的变化量为多少，最后，求出变化量最小的，用最初的逆序数求得最后结果。。。
其中模拟两个数交换之后逆序数的变化量解法：
如下：
有
a,b,c,d,e,f,g,h,i,g,k,l,m.....; 一系列数。
假设我们求交换 d 和 l 的数，其逆序数的变化量。
数列将变为：
a,b,c,l,e,f,g,h,i,g,k,d,m.....;
我们先看，在 d 到 l 这一段数中，有多少个比 d 大的数，记为 cnt1 ，那么，将 d 交换之后， 这 cnt1 个数将会各增加1个比其本身小的数，则最终总的逆序数则加 cnt1 ；
我们在看，有多少个比 d 小的数，记为 cnt2 ， 则 相对于 d 来说，最后少了 cnt2 个比 d 小的数， 则最后结果减 cnt2；
同理 对 l 进行一次与 d 相同的操作，则最后的结果变化量则为交换 d 与 l 的逆序数的变化量。
代码如下：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#define INF 0x7fffffff
using namespace std;
int num[1002];
int z[1002][1002];//统计逆序数的变化量。
int main()
{int n;while(~scanf("%d",&n)){memset(z,0,sizeof(z));for(int i=0; i<n; i++){scanf("%d",&num[i]);}int res=0;//求最初的逆序数for(int i=0; i<n; i++){int cnt=0;for(int j=i+1; j<n; j++){if(num[j]<num[i]){res++;//总的逆序数cnt--;}else if(num[j]>num[i])cnt++;z[i][j]=cnt;//统计与第一个交换数比较后的逆序数变化量}}for(int i=n-1; i>0; i--){int cnt=0;for(int j=i-1; j>0; j--){if(num[j]<num[i])cnt++;else if(num[j]>num[i])cnt--;z[j-1][i]+=cnt;//加上与第二个交换数比较后的逆序数变化量}}int m=0;//找到逆序数最小的变化量for(int i=0; i<n; i++)for(int j=i+1; j<n; j++)m=m>z[i][j]?z[i][j]:m;printf("%d\n",res+m);}
}
这篇关于FZOJ 2166 inversion的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
