小朋友排队

time limit per test 2 second memory limit per test 256 megabytes
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

题解

就是求一个数前面有多少个数比它大和后面有多少个数比它小
前面比它大的就是普通的逆序对时求的
后面比它小的要主要当后面全部比它小时也要加上 即在后面while里别忘了加

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.*;  
import java.util.*;
public class Main {
static long count;
static F[]temp;
public static void main(String[] args) throws NumberFormatException, IOException {
FastScanner sc=new FastScanner();
//Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
F[]shu=new F[n];
for(int i=0;i<n;i++){
int temp=sc.nextInt();
shu[i]=new F(temp,0);
}
temp=new F[n];
count=0;
mergeSort(shu,0,n-1);
for(int i=0;i<n;i++){
long t=shu[i].js;
//pw.println(t);
//pw.println(shu[i].js+" "+shu1[i].js);
//pw.println(shu1[i].num);
//pw.println(t);
count+=(1+t)*t/2;
}
pw.println(count);
pw.flush();
}

}
static void mergeSort(F[]shu,int l,int r){
if(l<r){
int mid=(l+r)/2;
mergeSort(shu,l,mid);
mergeSort(shu,mid+1,r);
merge(shu,l,mid,r);
}
}
static void merge(F[]shu,int l,int mid,int r){
int ll=l;
int index=l;
int rr=mid+1;
long k1=0;
long k2=0;
while(ll<=mid&&rr<=r){
if(shu[ll].num<=shu[rr].num){
shu[ll].js+=rr-mid-1;
temp[index++]=new F(shu[ll].num,shu[ll].js);
ll++;
}else{
shu[rr].js+=mid-ll+1;
temp[index++]=new F(shu[rr].num,shu[rr].js);
rr++;
}
}
//count+=(1+k1+k2)*(k1+k2)/2;
while(ll<=mid){
shu[ll].js+=r-mid;
temp[index++]=new F(shu[ll].num,shu[ll].js);
ll++;
}
while(rr<=r){
temp[index++]=new F(shu[rr].num,shu[rr].js);
rr++;
}
for(int i=l;i<=r;i++){
shu[i]=temp[i];
}
}
}
class F{
int num;
int js;
F(int a,int b){
num=a;
js=b;
}
}