题解:Parabolic sorting

题解:Parabolic sorting

地址:https://vjudge.net/problem/Gym-102780K

1.题意：

Professor R. is the greatest specialist in the field of discrete mathematics. He has already got bored with all the standard sorting algorithms, and has come up with a new algorithm — the parabolic array sorting algorithm.

Let there be an array of N different integer numbers ai. We want to sort it in such a way that the first part of the array strictly decreases, and the second part of the array strictly increases. In this case, we can only interchange the neighboring elements. Both the first and second parts of the array can be of zero length. The professor is interested in the following question: what is the minimum number of actions we need?

Input
In the input N+1 there is a number, the first of which is N (1≤N≤105). Then follow the numbers ai, whose module does not exceed 109.

Output
Print a single number — the answer to the problem.

2.思路：

目前网上找到两份题解，内容基本一致，但都讲的含糊不清。

考虑一个序列，我们先找到它最大的元素，它可以被放在两个位置，前半部分降序序列的尾部，或后半部分升序序列的前部。

我们所熟知的定理：只交换相邻的两数让序列变成升序，交换次数为逆序对数。

证明如下：考虑一个排列，先将其最大的数移至序列尾，次数为最大数与它后面的数组成的逆序对数。此时最后一位已定，再考虑前n-1个数的排列。

类比，如果要放在升序序列的尾部，那么它交换的最少次数为此序列中在a[i]前面且比a[i]小的数的数量。我们不妨称之为“正序对”

如果要放在降序序列的首部，那么它交换的最少次数为此序列中在a[i]后面且比a[i]小的数的数量。即为以a[i]为开头的逆序对数。

对于任意一个数，我们选择它的“正序对”与逆序对数最小的一个作为将它归位的步数即可。

3.代码:

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN = 1e6+7;
#define lowbit(x) (x)&(-x)
int c[MAXN],l[MAXN],r[MAXN],n;
struct node{
    int v,num;
}t[MAXN];
inline bool cmp(const node a,const node b){
    return a.v<b.v;
}
inline bool cmpNum(const node x,const node y){
    return x.num<y.num;
}
void Insert(int pos,const int x){
    while(pos<=n){
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}
long long sum(int pos){
    long long ans=0;
    while(pos>0){
        ans+=c[pos];
        pos-=lowbit(pos);
    }
    return ans;
}
inline int Min(const int a,const int b){
    return a<b?a:b;
}
int main(){
    long long ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i].v);
        t[i].num=i;
    }
    t[n].num=n;
    sort(t+1,t+n+1,cmp);
    int posMin = t[1].num;
    for(int i=1;i<=n;i++){
        t[i].v=i;
    }
    sort(t+1,t+n+1,cmpNum);
    for(int i=1;i<=n;i++){
        l[i]=sum(t[i].v);
        Insert(t[i].v,1);
    }
    memset(cPre,0,sizeof(cPre));
    for(int i=n;i>=1;i--){
        r[i]=sum(t[i].v);
        Insert(t[i].v,1);
    }
    for(int i=1;i<=n;i++){
        ans+=Min(l[i],r[i]);
    }
    cout<<ans;
    return 0;
}