汉中市网站建设,免费企业信息查询,精美合同网站建设,常用的设计网站题意#xff1a;
给出n个数#xff08;0~n-1#xff0c;每个数仅出现一次#xff09;,问它长为n的循环序列中逆序对最少的数量。
多种解法#xff1a;暴力树状数组分治规律推导公式
题目#xff1a;
The inversion number of a given number sequence a1, a2, …, an…题意
给出n个数0~n-1每个数仅出现一次,问它长为n的循环序列中逆序对最少的数量。
多种解法暴力树状数组分治规律推导公式
题目
The inversion number of a given number sequence a1, a2, …, an is the number of pairs (ai, aj) that satisfy i j and ai aj.
For a given sequence of numbers a1, a2, …, an, if we move the first m 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, …, an-1, an (where m 0 - the initial seqence) a2, a3, …, an, a1 (where m 1) a3, a4, …, an, a1, a2 (where m 2) … an, a1, a2, …, an-1 (where m n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10 1 3 6 9 0 8 5 7 4 2
Sample Output
16
分析
第一种解法暴力
1.为了实现环,将数组扩到两倍a[in]a[i]; 2.求出初始串的状态即最小逆序对; 3.由1直接往后遍历每次选取连续的n个数即效果等同于每次把最后的元素放置最前即可实现环。
AC代码
/**暴力*/
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int M1e410;
int a[M],b[M];
int n,ans,num,cnt;
int main()
{while(~scanf(%d,n)){memset(b,0,sizeof(b));for(int i0;in;i){scanf(%d,a[i]);a[in]a[i];}ans0;for(int i0;in;i){for(int ji1;jn;j)if(a[i]a[j])b[i];ansb[i];}for(int i1;in-1;i){cnt0;for(int ji;jin-1;j){if(a[j]a[i-1])b[j];cntb[j];}if(anscnt)anscnt;}printf(%d\n,ans);}return 0;
}第二种解法树状数组求逆序数。
1.由题意n个数0~n-1每个数仅出现一次用树状数组来维护[0,n)的区间。 2.每次读入一个数将该数存入树状数组b[]用树状数组来维护[0,n)的区间和。 3.每次先求出区间[ai1,n)的和即为ai之前比ai大的数字的个数。 4.由前面求出初始串的状态即最小逆序对 5.如序列a1,a2,a3,a4,a5它的逆序对数量ssum(num(akai,ki));序列变为a2,a3,a4,a5,a1和上一个序列相比变化分为两步。 1拿走a1,逆序对减少a1 整个序列是0~n-1且每个数字仅出现一次个 2将a1 放入序列尾部;加入序列尾部,逆序对增加n-1-a1个这样就可以递推求解各序列的逆序对个数。
#includestdio.h/**树状数组求逆序数*/
#includestring.h
#includealgorithm
using namespace std;
const int M5e310;
int n,ans,num,mi;
int a[M],b[M];
int lowbit(int x)
{return x(-x);
}
int query(int x)///每次先求出区间[ai1,n)的和,即为ai之前比ai大的数字的个数
{int num0;x1;while(xn){numb[x];xlowbit(x);}return num;
}
void update(int pos,int val)///用树状数组来维护[0,n)的区间和
{while(pos0){b[pos]val;pos-lowbit(pos);}
}
int main()
{while(~scanf(%d,n)){ans0;memset(b,0,sizeof(b));for(int i0; in; i){scanf(%d,a[i]);update(a[i]1,1);///每次读入一个数将该数存入树状数组b[]ansquery(a[i]1);///查询前面是否有比该数大的数即为逆序数}mians;for(int i0; in; i){ansans(n-1)-2*a[i];/**如序列a1,a2,a3,a4,a5它的逆序对数量ssum(num(akai,ki));
序列变为a2,a3,a4,a5,a1和上一个序列相比变化分为两步拿走a1和将a1 放入序列尾部;拿走a1,逆序
对减少a1 整个序列是0~n-1且每个数字仅出现一次个加入序列尾部,逆序对增加n-1-a1个这样就可
以递推求解各序列的逆序对个数。*/if(ansmi)mians;}printf(%d\n,mi);}return 0;
}第三种解法分治求逆序数
1.用分治求出初始串的状态每次把最后的元素放置最前即可实现环。 2.每次移动时与前面树状树状的后面解法一样 1所有data[i]后面比他小的元素逆序数 -10~k-1k个 2所有data[i]后面比他大的元素逆序数 1n-1-k个 3逆序数改变总数是 n - 2*k - 1k data[i] 枚举不同的首元素输出最小的逆序数即可。
#include stdio.h
#include stdlib.h
const int M5e310;
int a[M];
int b[M];
int c[M];
int dfs(int aa,int bb)
{if (aabb){int Ldfs(aa,(aabb)/2);int Rdfs((aabb)/21,bb);int numLR,totaa;int xaa,y(aabb)/2;int u(aabb)/21,vbb;while(xy||uv)if(uv(xy1||a[x]a[u])){b[tot]a[u];numy-x1;//计算A B 中的逆序数}elseb[tot]a[x];for(int iaa;ibb;i)a[i]b[i];return num;}elsereturn 0;
}int main()
{int n;while (~scanf(%d,n)){for( int i 1 ; i n ; i )scanf(%d,a[ i ]);for ( int i 1 ; i n ; i )c[ i ] a[ i ];int ans dfs( 1, n );int mi ans;for ( int i 1 ; i n ; i ){ans n - 2*c[ i ] - 1;if ( ans mi )mians;}printf(%d\n,mi);}return 0;
}
