點選這裡即可送出代碼
Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K |
| Total Submissions: 78254 | Accepted: 29347 |
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
題目大意：給你一串數先，現在進行冒泡排序，問你最少幾次能将這串數字排成從大到小的标注上升順序？
要做的第一步就是将資料離散化，到底什麼是離散化呢？就是将很大的區間進行映射，使得能被操作的區間變得相對集中
就像這道題目：999999999用int是可以存的下的，500000大的數組也是可以開出來的，那麼為什麼要進行離散化操作呢？做這道題之前我都不知道什麼叫離散化。。。 其實999999999這個數字相對于500000這個數字來說是很大的， 是以如果用數組位存儲的話，那麼需要999999999的空間來存儲輸入的資料。這樣是很浪費空間的，題目也是不允許的，是以這裡想通過離散化操作， 使得離散化的結果可以更加的密集。
簡言之就是開一個大小為這些數的最大值的樹狀數組
還有就是怎麼進行離散化呢？離散化是一種常用的技巧，有時資料範圍太大，可以用來放縮到我們能處理的範圍；
因為其中需排序的數的範圍0---999 999 999；顯然數組不肯能這麼大；而N的最大範圍是500 000；故給出的數一定可以與1.。。。N建立一個一一映射；
我們可以用一個結構體
struct Node{
int val;
int pos;
}p[510000];
和一個數組a[510000];
其中val就是原輸入的值，pos是下标；
然後對結構體按val從小到大排序；
此時，val和結構體的下标就是一個一一對應關系，
而且滿足原來的大小關系
接下來
for(i=1;i<=N;i++)
a[p[i].pos]=i;
然後a數組就存儲了原來所有的大小資訊
比如 9 1 0 5 4 ------- 離散後aa數組
就是 5 2 1 4 3;
推薦自己動手寫一寫
還有一些其他的做法，這裡有一篇大佬的blog講的超詳細離散化思想和兩種代碼；
這道題的下一個難點就是求這個冒泡排序數目了，這就涉及了一些偏序關系的内容：
說句實在的我還真沒弄懂，但是隻需要明白一點 就可以把這個題給AC 那就是求逆序對
再者就是樹狀數組的使用，我也是初學者，學長告訴我這是闆子，但我老是感覺他在騙我，可能暫時是闆子，以後就不是了吧
奉上我的AC代碼先 Orz
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int mm=5e5+5;
int n;
int a[mm],b[mm];
struct node{
int val;
int pos;
}pp[mm];
int cmp(node x,node y){
return x.val<y.val;
}
int lbt(int t){
return t&-t;
}
void up(int pos,int k){//在pos位置上加上k
while(pos<=n){
b[pos]+=k;
pos+=lbt(pos);
}
}
long long sum(int pos){//求[1,pos]的和
long long res=0;
while(pos>0){
res+=b[pos];
pos-=lbt(pos);
}
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n){
for(int i=1;i<=n;i++){
scanf("%d",&pp[i].val);
pp[i].pos=i;
}
sort(pp+1,pp+n+1,cmp);
for(int i=1;i<=n;i++)
a[pp[i].pos]=i;//離散化
long long res=0;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++){
up(a[i],1);
res+=i-sum(a[i]);
}
printf("%lld\n",res);
}
return 0;
}