题目：给定一个数字串0 - N-1，每次可以移动首位数字到末尾，求最少的逆序对的组合方式。先求出原序列的逆序对，再用数学公式算出最佳值。
假设有 10 个数，依题义为 0 - 9，那么首位为4的话，从首位移动到末尾产生新的逆序对为0 - 9中大于4的数字减去少于4的数。
代码如下：
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int N, num[5005];
void getint( int &t )
{
char c;
while( c= getchar(), c< '0'|| c> '9' ) ;
t= c- '0';
while( c= getchar(), c>= '0'&& c<= '9' )
{
t= t* 10+ c- '0';
}
}
inline int get( int x )
{
return N- 1- 2* x;
}
int main()
{
while( scanf( "%d", &N )!= EOF )
{
int cnt= 0;
for( int i= 1; i<= N; ++i )
{
getint( num[i] );
for( int j= 1; j< i; ++j )
{
if( num[i]< num[j] )
{
cnt++;
}
}
}
int min= cnt, temp= cnt;
for( int i= 1; i<= N; ++i )
{
temp+= get( num[i] );
if( temp< min )
{
min= temp;
}
}
printf( "%d\n", min );
}
}
下面的写法为线段树版，为什么要用线段树呢，注意上面的程序，在求逆序对的时候，我们都是暴力的遍历。现假设前面的数据中出现了某一区间的数都已经出现了，那么后面的数小于该区间的话，就可以之间处理了，不用一个一个的去比较，更像是把原先无序的数字，经过线段树变得具有一定的结构，便于后面的查询。
代码如下：
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int N, rec[5005];
struct Node
{
int l, r, cnt;
}t[15005];
void creat( int p, int l, int r )
{
t[p].l= l, t[p].r= r;
t[p].cnt= 0; // 在创建一棵线段树的时候每个节点都应将所衔的数置零
if( r- l> 1 )
{
creat( p<< 1, l, ( l+ r )>> 1 );
creat( ( p<< 1 )+ 1, ( l+ r )>> 1, r );
}
}
void update( int p, int l, int r, int &temp )
{ // 更新得到逆序对的最新数据
if( t[p].l== l&&t[p].r== r )
{
temp+= t[p].cnt;
return;
}
int mid= ( t[p].l+ t[p].r )>> 1;
if( l>= mid )
{
update( ( p<< 1 )+ 1, l, r, temp );
}
else if( r<= mid )
{
update( p<< 1, l, r, temp );
}
else
{
update( p<< 1, l, mid, temp );
update( ( p<< 1 )+ 1, mid, r, temp );
}
}
void add( int p, int pos ) // 添加操作，在经过的区间都加1
{
t[p].cnt++;
if( t[p].r- t[p].l== 1 )
{
return;
}
else if( pos>= ( t[p].l+ t[p].r )>> 1 )
{
add( ( p<< 1 )+ 1, pos );
}
else
{
add( p<< 1, pos );
}
}
int get( int x )
{
return N- 1- 2* x;
}
int main( )
{
while( scanf( "%d", &N )!= EOF )
{
int min= 0x7fffffff, temp= 0;
for( int i= 1; i<= N; ++i )
{
t[i].cnt= 0;
}
creat( 1, 0, N+ 1 ); // 从0开始比编号
for( int i= 1; i<= N; ++i )
{
scanf( "%d", &rec[i] );
update( 1, rec[i]+ 1, N+ 1, temp ); // 寻找比rec[i]大的数
add( 1, rec[i] );
}
for( int i= 1; i<= N; ++i )
{
temp+= get( rec[i] );
if( temp< min )
{
min= temp;
}
}
printf( "%d\n", min );
}
}