MYF

HDU 5774 Bubble Sort

Posted on | In | | Visitors

题目链接

HDU 5774

题目类型：树状数组求逆序数

题目来源：2016年多校Round4

题目分析

题目大意

对n个数字冒泡排序，问，对于每一个数字，能到达的最大位置和最小位置的距离是多少

解析

分析一下题目中给出的冒泡排序代码，第一层for执行N次循环，第二层for表示从后往前，轻的泡泡往前冒，也就是说，小的一直往前换，大的被动的跟着小的换。也就是说，对于一个位置的数来讲，右边有多少比他小的数，他就要往右移多少次，左边有多少比他大的数字，他就要往左移动多少次。找到这个规律，发现就是求从左往中间每个点的逆序数，以及从中间每个点往右的顺序数。逆序数不难求，从左往右用树状数组更新即可。顺序数相当于是从右往左的逆序数，反向插入，求之前有多少逆序数即可。找到r[]和l[]之后，发现每个点所能到达的最大位置为pos[i]+r[i]，最小位置为min(pos[i]+r[i]-l[i], i)，求个差取个绝对值即可。

代码

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
81
82
83
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(checker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=100000+10;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int c[maxn],n,a[maxn],l[maxn],r[maxn],ans[maxn];
int lowbit(int x){
    return x&(-x);
}
void update(int pos, int val){
    while (pos<=n) {
        c[pos]+=val;
        pos+=lowbit(pos);
    }
}
int sum(int pos){
    int rt=0;
    while (pos>0) {
        rt+=c[pos];
        pos-=lowbit(pos);
    }
    return rt;
}
int main(){
    int T;
    scanf("%d",&T);
    for (int cas = 1; cas<=T; cas++) {
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
        }
        
        memset(c, 0, sizeof(c));
        for (int i=1; i<=n; i++) {
            update(a[i], 1);
            l[i]=i-sum(a[i]);
//            printf("%d ",l[i]);
        }
//        hi;
        memset(c, 0, sizeof(c));
        for (int i=n; i>=1; i--) {
            update(a[i], 1);
            r[i]=sum(a[i])-1;
//            printf("%d ",r[i]);
        }
//        hi;
        
        for (int i=1; i<=n; i++) {
            ans[a[i]]=abs(i+r[i]-min(i, i+r[i]-l[i]));
        }
        printf("Case #%d:",cas);
        for (int i=1; i<=n; i++) {
            printf(" %d",ans[i]);
        }
        printf("\n");
    }
}