?? pku2299.cpp
字號(hào):
#include <stdio.h>
int a[500001], b[500001];
__int64 change;
void merge(int, int, int);
void mergeSort(int first, int last)
{
if(first < last) {
int mid = (first + last) / 2;
mergeSort(first, mid);
mergeSort(mid+1, last);
merge(first, mid, last);
}
}
void merge(int p, int q, int r)
{
int i, j = 0;
int beginA = p, endA = q, beginB = q+1, endB = r;
while(beginA <= endA && beginB <= endB) {
if(a[beginA] <= a[beginB]) {
b[j++] = a[beginA++];
} else {
b[j++] = a[beginB++];
change += q - beginA + 1;
}
}
while(beginA <= endA) {
b[j++] = a[beginA++];
}
while(beginB <= endB) {
b[j++] = a[beginB++];
}
for(i = 0; i < j; i++) {
a[p+i] = b[i];
}
}
int main()
{
int N, i;
while (scanf("%d", &N) != -1 && N)
{
for (i = 0; i < N; i++)
{
scanf("%d", &a[i]);
}
change = 0;
mergeSort(0, N - 1);
printf("%I64d\n", change);
}
return 0;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -