这阵子巨忙，呜呜呜....
上周末打了第十四届蓝桥杯的校内赛，总的来说，题目是很简单的，不过其中的压轴题挺有意思，所以我打算来一发博客记录记录这道算法题。废话不多说了，上题：
小蓝有一个序列 a[1], a[2], ..., a[n]，每次可以交换相邻的两个元素，代价为两个元素中较大的那个。
请问，要通过交换将序列变为从小到大递增的序列，总代价最少为多少？
输入一行包含一个整数 n ，表示序列长度。
第二行包含 n 个整数，表示给定的序列。
输出一行包含一个整数，表示最少代价的值。
样例输入1
4
1 5 2 1
样例输出1
12
评测用例规模与约定
对于 30% 的评测用例，1 <= n <= 1000, 1 <= a[i] <= 1000。
对于 60% 的评测用例，1 <= n <= 50000, 1 <= a[i] <= 50000。
对于所有评测用例，1 <= n <= 1000000, 1 <= a[i] <= 1000000。
思路：
首先题目说的是，每次交换相邻的两个，取两者较大的作为代价，同时要保证最后的结果是最小的。 举个例子： 1 5 2 1，我们要变成 1 1 2 5 这样才符合题目要求对吧 ？ 那么怎么让他代价最小呢？ 拿 1 5 2 1来看，我们设ans = 0 ,一直看到 5 比 2 大，要交换一下 ,ans+=5,同时变成 1 2 5 1 ，5又比1 大，ans+=5, 变成1 2 1 5 ，这样子我们成功解决掉最大的数5了，再也不用加到它的值了，然后看2 与 1 交换 ans+=2 变成 1 1 2 5 ,就是我们想要的答案了。所以其实我们会发现，5后面比他小的数有2个 ans+=(5*2); 2后面有 1个比他小 ans+= (2*1); 不就是把问题转换为 求每个数后面有多少个比它大的（其实就是逆序对），然后将逆序对的个数乘以这个数的值，就是答案了！！！
所以我们可以先来一波暴力解法：
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner cin = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
int n = cin.nextInt();
int num[] = new int[n];
for(int i = 0;i<n;i++) {
num[i] = cin.nextInt();
}
long ans = 0;
for(int i = 0;i<n;i++) {
for(int j = i+1;j<n;j++) {
if(num[i] > num[j]) {
ans+=num[i];
}
}
}
System.out.println(ans);
}当然，这个解法O（n²）必定会超时，不过可以骗一些分，所以考虑使用其他解法。
大家先想一想，上面的暴力解法，最大的问题就是把比num[i]大的个数全都遍历了，导致的复杂度增加，所以我们可以利用归并排序算法，在合并过程中，有一边肯定比另一边的大的特点来简化时间复杂度。具体做法看图的例子：
我们拿一个数组num[1,5,40,7,19,10]来从大到小排序看：我们肉眼就知道逆序对是4 （<40,7><40,19><40,10><19,10>）
具体看代码：
public static void finish(int l,int r,int mid) {
int i = l;
int j = mid;
int p = l;
while(i < mid && j <= r) {
if(num[i] <= num[j]) {
temp[p++] = num[j++];
}
else { //如果右边有比它大的，因为右边已经排序了，所以直接乘以个数。
ans += (num[i]* (r - j + 1));
temp[p++] = num[i++];
}
}
while( i< mid) {
temp[p++] = num[i++];
}
while(j <= r) {
temp[p++] = num[j++];
}
for(int start = l; start <= r;start++) {
num[start] = temp[start];
}
}
public static void fenzhi(int l,int r) {
if(l < r) {
int mid = (l+r)/2;
fenzhi(l,mid);
fenzhi(mid+1 , r);
finish(l,r,mid+1);
}
}
public static int n,temp[],num[];
public static long ans = 0;
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner cin = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
n = cin.nextInt();
num = new int[n];
for(int i = 0;i<n;i++) {
num[i] = cin.nextInt();
}
temp = new int[n];
fenzhi(0,n-1);
System.out.println(ans);
}其实这个也挺好理解，我们先要进行离散化，为啥离散化呢？原因就是：比如 {1,3,9,100,5}这5个数，我们如果我们创一个数组来保存他们的值，那么需要开到101欸，只要5个数开到101很亏，所以我们要用离散化来解决这个问题，我们给它们一个下标pi，value{1,3,9,100,5} ->pi {1,2,3,4,5} 然后按照value值来排序，得到的就是 value{1,3,5,9,100} -> pi{1,2,5,3,4},我们每次遍历数组把pi放进去，然后查一下1~pi-1放进了多少个，就可以知道有多少个逆序对了，再乘以数组就ok.
public static class stu{
int pi;
int value; //离散化
public stu(int pi, int value) {
this.pi = pi;
this.value = value;
}
}
public static int lowbit(int x) {
return x & (-x);
}
public static void add(int x) {
while(x <= n) {
BT[x] ++;
x += lowbit(x);
}
}
public static int get(int x) {
int ans = 0;
while(x > 0) {
ans += BT[x];
x -= lowbit(x);
}
return ans;
}
public static int num[];
public static int BT[],n;
public static stu tree[];
public static long ans = 0;
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner cin = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
n = cin.nextInt();
num = new int[n];
for(int i = 0;i<n;i++) {
num[i] = cin.nextInt();
}
tree = new stu[n];
BT = new int[n+1];
for(int i = 0;i<n;i++) {
tree[i] = new stu(i+1, num[i]);
}
Arrays.sort(tree,new Comparator<stu>() {
@Override
public int compare(stu o1, stu o2) {
// TODO 自动生成的方法存根
return o1.value == o2.value ? o1.pi - o2.pi : o1.value - o2.value;
}
});
//序列化
int ans = 0;
for(int i = 0;i<n;i++) {
add(tree[i].pi);
ans += (tree[i].value*(i - get(tree[i].pi - 1))); //查一下有多少个比他小的
}
System.out.println(ans);
}线段树也是一样的思路，就是变成了线段树的写法
public static PrintWriter pw =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static int Int(){
try {
st.nextToken();
} catch (IOException e) {
// TODO 自动生成的 catch 块
e.printStackTrace();
}
return (int)st.nval;
}
public static class stu{
int pi;
int value;
public stu(int pi, int value) {
super();
this.pi = pi;
this.value = value;
}
}
public static class MyComparator<T> implements Comparator<T>{
@Override
public int compare(T o1, T o2) {
// TODO 自动生成的方法存根
stu a1 = (stu)o1;
stu a2 = (stu)o2;
if(a1.value == a2.value) {
return a1.pi - a2.pi;
}
else {
return a1.value - a2.value;
}
}
}
public static void build(int l,int r,int pi) {
Arrays.fill(tree, 0);
}
public static int search(int l,int r,int pi,int nx ,int ny ) {
if(nx <= l && r <= ny) {
return tree[pi];
}
int mid = (l+r)/2;
int ans = 0;
if(mid >= nx) {
ans += search(l,mid,pi*2,nx,ny);
}
if(mid < ny) {
ans += search(mid+1,r,pi*2+1,nx,ny);
}
return ans;
}
public static void add(int l,int r,int pi,int fill) {
if(l > r) {
return ;
}
if(l == fill && r == fill) {
tree[pi] ++;
return ;
}
int mid = (l + r)/2;
if(fill <= mid) {
add(l,mid,pi*2,fill);
}
else {
add(mid+1,r,pi*2+1,fill);
}
tree[pi] = tree[pi*2] + tree[pi*2+1];
}
public static int n,tree[],lazy[];
public static stu mp[];
public static void main(String[] args) {
// TODO 自动生成的方法存根
n = Int();
mp = new stu[n];
for(int i = 0;i<n;i++) {
int num = Int();
mp[i] = new stu(i+1,num);
}
Arrays.sort(mp,new MyComparator<stu>());
pw.flush();
tree = new int[n*4+1];
lazy = new int[n*4+1];
build(1,n,1);
long ans = 0;
for(int i = 0;i< n;i++) {
add(1,n,1,mp[i].pi);
int kk = 0;
if(mp[i].pi-1 > 0) {
kk = search(1,n,1,1,mp[i].pi-1);
}
ans += (mp[i].value * (i - kk) );
}
pw.println(ans);
pw.flush();
}