Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
这道题是树状数组的入门题 所以恭喜我们又要学习并开始运用到一个有意思的数据结构了
-
题意
按照白话来说就是现在有一个无序序列 我们只能交换相邻元素 把无序序列变成升序排列 求最小步数 -
分析
对于这道题的分析是两个方面 首先我们需要转化问题 即题到底想让我们干什么 我们仔细观察不难发现 我们要做的就是计算每一个数前面大于它本身的数有多少 即逆序数 这就把问题转化为了一个区间求和问题 这就是树状数组的强项 我们可以在O(logn)内完成 大致思路就是这样 我们又发现了一个问题 就是数据范围很大 即[0,999999999] 显然我们要以数字大小为数组下标 而且这题与数字本身并没有什么太大联系 所以自然而然想到离散化 这题到这里就结束了 注意数字最多五十万 即最大答案数超过int范围 开long long 即可 -
总结
BIT是一个优秀的数据结构 虽然比不上线段树 但是胜在代码简洁 有了思路短时间即可完成 所以需要花费一些时间来训练
AC代码
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<cstdlib>
#include<utility>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
struct node{
int w,index;
bool operator<(const node &tmp)const{
return w<tmp.w;
}
};
ll m,n,num;
ll bit[500010];
node book[500010];
ll lowbit(ll x){
return x&-x;
}
ll add(ll x){
for(int i=x;i<=500010;i+=lowbit(i)){
bit[i]+=1;
}
}
ll sum(ll x){
ll ans = 0;
for(int i=x;i>0;i-=lowbit(i)){
ans+=bit[i];
}
return ans;
}
int main()
{
while(cin >> m && m){
num = 0;
memset(bit,0,sizeof(bit));
for(int i=1;i<=m;++i){
cin >> n;
book[i].w = n;
book[i].index = i;
}
sort(book+1,book+1+m);
for(int i=m;i>=1;--i){
num+=sum(book[i].index); //利用从后往前排除离散化留下的同一个数字离散为不同数字的情况 代码量少一点
add(book[i].index);//再或者就是离散化费点事 同一个数字为离散为相同的值 就可以前后都ok了 总之就是好想不好写 好写不好想
}
cout << num << endl;
}
return 0;
}