历届试题 小朋友排队(树状数组求逆序数)

2017年02月23日 16点热度 0人点赞 0条评论
问题描述
  n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。

  每个小朋友都有一个不高兴的程度。开始的时候,所有小朋友的不高兴程度都是0。

  如果某个小朋友第一次被要求交换,则他的不高兴程度增加1,如果第二次要求他交换,则他的不高兴程度增加2(即不高兴程度为3),依次类推。当要求某个小朋友第k次交换时,他的不高兴程度增加k。

  请问,要让所有小朋友按从低到高排队,他们的不高兴程度之和最小是多少。

  如果有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。

输入格式
  输入的第一行包含一个整数n,表示小朋友的个数。
  第二行包含 n 个整数 H1 H2 … Hn,分别表示每个小朋友的身高。
输出格式
  输出一行,包含一个整数,表示小朋友的不高兴程度和的最小值。
样例输入
3

3 2 1
样例输出
9
样例说明
  首先交换身高为3和2的小朋友,再交换身高为3和1的小朋友,再交换身高为2和1的小朋友,每个小朋友的不高兴程度都是3,总和为9。
数据规模和约定
  对于10%的数据, 1<=n<=10;
  对于30%的数据, 1<=n<=1000;
  对于50%的数据, 1<=n<=10000;

  对于100%的数据,1<=n<=100000,0<=Hi<=1000000。

#include  
#include  
#include  
#define INF 1000010  
using namespace std;  
int t[INF]={0},a[100010]={0},b[100010]={0},n;  
long long total[100000]={0};  
int lowbit(int x){  
    return x&-x;  
}  
void add(int x){  
    while(x0){  
        n+=t[x];  
        x-=lowbit(x);  
    }  
    return n;  
}  
int main(){  
    scanf("%d",&n);  
    for(int i=1;i0;i--){  
        b[i]+=sum(a[i]);  
        ans+=total[b[i]];  
        add(a[i]+1);  
    }  
    printf("%lldn",ans);  
    return 0;  
}  
未经允许不得转载!历届试题 小朋友排队(树状数组求逆序数)

update

纸上得来终觉浅, 绝知此事须躬行。