TIOJ 1080
題敘
https://tioj.ck.tp.edu.tw/problems/1080
逆敘數對模板題
對於一個數列 $S$ 若 $S$ 的第 $i$ 項 $s_i$ 與第 $j$ 項 $s_j$ 符合 $s_i>s_j$ ，並且 $i<j$ ，那麼我們說 $(i,j)$ 是一個逆序數對。請問給定 $S$ ，總共有多少個逆序數對
想法
對於一個元素來說，他的逆敘數對數量會跟在這個元素之後比該元素還小的數量相同
也就是說，我們的目的是要每個元素找到符合這樣條件的數量總和
如果今天我們拿到的是一個已經排序好的序列，保證元素是嚴格遞增
那麼我們可以很快的知道每個元素的逆敘述對有多少個
| 元素 |
1 |
2 |
3 |
4 |
5 |
| 逆敘數對量 |
4 |
3 |
2 |
1 |
0 |
換個角度來想，也就是我們希望能做出一個具有規律性的序列，如此一來就可以很快速的解出每個元素的答案
可以利用 merge sort 來處理這樣的問題
在排序的過程當中，我們會不斷地將序列分成兩個部分
而當左邊的元素 $i$ 大於右邊的元素 $j$ 時，我們可以很明顯的知道
與 $i$ 以及 $i$ 後面屬於左邊的元素和 $j$ 必定會是逆敘數對
因此每次遇到這種情況就加上還在左邊的元素數量
Code
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
|
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define pii pair<int,int>
using namespace std;
int n,Case=1,arr[2000100],ans=0,tmp[2000100];
void merge(int L,int R){
int mid=(L+R)>>1;
for(int i=L,j=mid+1,k=L ; k<=R ; k++){
if(i>mid)
tmp[k]=arr[j++];
else if(j>R)
tmp[k]=arr[i++];
else if(arr[i]<=arr[j])
tmp[k]=arr[i++];
else{
ans+=(mid-i+1);
tmp[k]=arr[j++];
}
}
for(int i=L ; i<=R ; i++)
arr[i]=tmp[i];
}
void merge_sort(int L,int R){
int mid=(L+R)>>1;
if(L==R)
return;
merge_sort(L,mid);
merge_sort(mid+1,R);
merge(L,R);
}
signed main(){
IOS;
while(cin>>n && n){
ans=0;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
merge_sort(0,n-1);
cout<<"Case #"<<Case++<<": "<<ans<<'\n';
}
return 0;
}
|
複雜度
與 merge sort 相同 $O(NlogN)$