题目链接：点击打开链接
Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 68838 | Accepted: 25801 |
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
题目大意：就是求逆序数
思路：①归并排序 ②树状数组
归并排序思想：可以从two pointers里体现出来（把A数组和B数组合并成递增的C数组）---A和B都是递增的数列
int merge(int A[], int B[], int C[], int n, int m) {
int i = 0, j = 0, index = 0;//i 指向 A[0] j指向B[0]
while(i < n && j < m) {//其中一个到最后，就结束了
if(A[i] < B[j])// 谁小谁放入C数组，并后移1位
C[index++] = A[i++];
else
C[index++] = B[j++];
} //把另一个没有到最后的 直接放进去 （A和B都是递增的数组）
while(i < n) C[index++] = A[i++];
while(j < n) C[index++] = B[j++];
}归并排序就是这样的思想，下面的代码有所改动，可以比较着理解一下。
归并排序AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX = 500010;
int a[MAX], temp[MAX];//temp临时合并的数组
long long cnt; // 会爆int
int n;
void merge(int l, int m, int r) {//l到r 合并
int i = l;
int j = m + 1;
int k = l;//这个重要
while(i <= m && j <= r) {//two pointers思想
if(a[i] > a[j]) {
cnt += j - k; //逆序数
temp[k++] = a[j++];
} else temp[k++] = a[i++];
}
while(i <= m) temp[k++] = a[i++];
while(j <= r) temp[k++] = a[j++];
for(int i = l; i <= r; i++) { //把temp 赋值给 a数组（排完了）
a[i] = temp[i];
}
}
void mergesort(int l, int r) {//分治
if(l < r) {
int m = (l+r) / 2;
mergesort(l, m);
mergesort(m+1, r);
merge(l, m, r);
}
}
int main() {
while(~scanf("%d", &n)) {
if(n == 0)
break;
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
cnt = 0;
mergesort(0, n-1);//0~n-1
printf("%lld
", cnt);
}
}②树状数组AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
int pos;
int zhi;
}stu[500010];//离散化处理
int n, x;
bool cmp(node a, node b) {
return a.zhi < b.zhi;
}
//存数组
int sum[500010];
int b[500010];
//树状数组操作
void update(int pos, int val) {
while(pos <= n) {
sum[pos] += val;
pos += (pos & (-pos));
}
}
int query(int pos) {
int rec = 0;
while(pos > 0) {
rec += sum[pos];
pos -= (pos & (-pos));
}
return rec;
}
int main() {
while(~scanf("%d", &n)) {
if(n == 0)
break;
for(int i = 1; i <= n; i++) {//离散化处理
scanf("%d", &stu[i].zhi);
stu[i].pos = i;
}
sort(stu+1, stu+n+1, cmp);
for(int i = 1; i <= n; i++) {
b[stu[i].pos] = i;
}
memset(sum, 0, sizeof(sum));
long long nxs = 0;
for(int i = 1; i <= n; i++) {//操作
update(b[i], 1);//该位置加1
int temp = query(b[i]);//前缀和
nxs += (i - temp);//前面有几个空位（0）
}
printf("%lld
", nxs);
}
}