Tag: #hdu4911 #逆序數(shù)對(duì)
題目（原題目：HDU 4911）
bobo has a sequence a 1,a 2,…,a n. He is allowed to swap two adjacent（相鄰） numbers for no more than k times.
Find the minimum number of inversions after his swaps.
Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and a i>a j.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).
Output
For each tests:
A single integer denotes the minimum number of inversions.
Sample Input
3 1 2 2 1 3 0 2 2 1Sample Output
1 2
? 本題的要點(diǎn)是求一個(gè)數(shù)列的逆序數(shù)(對(duì))，我們先來看一下逆序數(shù)對(duì)的簡單定義：
在一個(gè)排列中，如果一對(duì)數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個(gè)逆序。一個(gè)排列中逆序的總數(shù)就稱為這個(gè)排列的逆序數(shù)。
如2431中，21，43，41，31是逆序，逆序數(shù)是4。
? 那么該如何求逆序?qū)?/strong>：
方法如下：
考察每一位，判斷從這一位往后有多少小于該位的，結(jié)果累加，得到最后結(jié)果。
例如，2,4,3,1 先判斷2，之后有1是小于2的，結(jié)果+1，再判斷4，之后3,1都小于4，結(jié)果+2，判斷3時(shí)，結(jié)果再+1，最后得到結(jié)果4.
? 很好理解，那么如何使用算法實(shí)現(xiàn)：當(dāng)然，我們可以用兩重循環(huán)暴力求解，但是顯而易見O(x2)的復(fù)雜度非常高；更高效的方式有：歸并排序、樹狀數(shù)組、線段樹。
? 本文為了迎合課上學(xué)習(xí)的歸并排序，所以選擇歸并排序算法來解。
? 歸并排序：主要思想是將整個(gè)序列分成兩部分，分別遞歸將這兩部分排好序之后，再和并為一個(gè)有序的序列。
? 在合并的過程中是將兩個(gè)相鄰并且有序的序列合并成一個(gè)有序序列，如以下一個(gè)無序列和分成的兩個(gè)有序序列
Seq： 3 4 5 2 6 8 9
Seq1：3 4 5
Seq2：2 6 8 9
合并成一個(gè)有序列:
Seq*：2 3 4 5 6 8 9
? 對(duì)于序列seq1中的某個(gè)數(shù)a[i],序列seq2中的某個(gè)數(shù)a[j]，如果a[i]<a[j],沒有逆序數(shù)，如果a[i]>a[j]，那么逆序數(shù)為seq1中a[i]后邊元素的個(gè)數(shù)(包括a[i])，即len1-i；
? 這樣累加每次遞歸過程的逆序數(shù)，在完成整個(gè)遞歸過程之后，最后的累加和就是逆序的總數(shù)。不難理解。
? 題中還提到只可交換相鄰的數(shù)字，這里引入一個(gè)逆序數(shù)定理
逆序數(shù)定理，當(dāng)逆序?qū)?shù)大于0時(shí)，若ak<ak+1,那么交換后逆序?qū)?shù)+1，反之-1。
? 這個(gè)其實(shí)也不難理解。
完整代碼
#include<iostream>
#include<string>
using namespace std;
#define ll long long
ll cnt ;
void Merge(int* A, int p, int q, int r) //根據(jù)算法導(dǎo)論改寫
{
int n1 = q - p + 1;
int n2 = r - q;
int i, j, k;
int *L = new int[n1 + 1];
int *R = new int[n2 + 1];
for(i= 0;i< n1;i++)
{
L[i] = A[p + i];
}
for(j= 0;j< n2;j++)
{
R[j] = A[q + j + 1];
}
L[n1] = INT_MAX;//書中的哨兵牌，表示正無窮,這里用INT_MAX來代替。
R[n2] = INT_MAX;
for(i= 0,j= 0,k= p;k<= r;k++)
{
if (L[i]<=R[j])
{
A[k]= L[i];
i++;
}
else //L[i]>R[j]出現(xiàn)逆序
{
A[k]= R[j];
j++;
cnt += (n1 - i); //根據(jù)逆序數(shù)定理添加的代碼
}
}
}
void MergeSort(int* A,int p,int r)
{
if(p< r)
{
int q = (p+ r)/2;
MergeSort(A,p,q);
MergeSort(A,q+1,r);
Merge(A,p,q,r);
}
}
int main()
{
/*int n, k, A[1000000];//n<=10^5
while(cin>>n>>k)
{
cnt = 0;
for(int i =0;i < n;i++)
cin>>A[i];
MergeSort(A,0,n-1);
cnt -= k;
if(cnt<0) cnt=0;
cout<<cnt<<endl;
}*/
//cin和cout效率屬實(shí)差勁
int n,k;
int a[10000000];
while(scanf("%d%d",&n,&k)!=EOF)
{
cnt=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
MergeSort(a,0,n-1);
printf("%lld\n",max((ll)0,cnt-k));
}
}
參考文章：
https://blog.csdn.net/crescent__moon/article/details/38424829
https://www.cnblogs.com/neopenx/p/4465348.html
https://blog.csdn.net/acm_jl/article/details/51147010
