HDU 4911（逆序数对）

题目

bobo has a sequence $a_1,a_2,\dots ,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\le i<j\le n$ and $a_i>a_j$.

输入

The input consists of several tests.For each tests:
The first line contains 2 integers $n,k(1\le n\le 10^5,0\le k\le 10^9)$.
The second line contains n integers $a_1,a_2,\dots ,a_n(0\le a_i\le 10^9)$.

输出

For each tests:
A single integer denotes the minimum number of inversions.

样例输入

3 1
2 2 1
3 0
2 2 1

样例输出

1
2

题目分析

本题为求一串数字中，经过最多$k$次相邻位互换后，转变后数字中还存在的“逆序数对”个数。
可经分析的得知，每一次互调后，最多可减少一对“逆序数对”，即一次测试中最多可减少$k$个”逆序数对“。则我们可以通过计算出原数字中的”逆序数对“总数，随后判定其与$k$值的大小关系，若小于$k$，则最少的”逆序数对“为$0$,若大于$k$，则最少数目为差值。

方法1：采用归并排序

算法复杂度：$O(n?log(n))$

代码

#include<iostream>
using namespace std;long long int cnt = 0,k,ans;//若为int则会超出范围
int n;
//归并排序并计数
void MergeAndCount(int a[],int start,int middle,int end,int tmp[])
{
    int pa = start,pt = middle+1,pc=-1;while(pa <= middle && pt <= end){
    if(a[pa] > a[pt])//降序排列{
    tmp[++pc] = a[pa++];cnt += end-pt+1;}elsetmp[++pc] = a[pt++];}while(pa<=middle)tmp[++pc] = a[pa++];while(pt<=end)tmp[++pc] = a[pt++];for(int i = 0;i<end-start+1;++i)a[start+i]=tmp[i];
}void MergeSort(int a[],int start,int end,int tmp[])
{
    if(start < end){
    int middle = start + (end-start)/2;MergeSort(a,start,middle,tmp);MergeSort(a,middle+1,end,tmp);MergeAndCount(a,start,middle,end,tmp);}
}int main()
{
    int a[100005],b[100005];//储数数组与中间过程数组int t,i;while(cin >> n && n!=EOF){
    cin >> k;t = n,i=-1;cnt = 0;while(t--)cin >> a[++i];MergeSort(a,0,n-1,b);if(cnt > k)//判定ans = cnt - k;elseans = 0;cout << ans << endl;}return 0;
}

运算结果

方法2：采用循环暴力求解

算法复杂度：$O(n^2)$ (会超时)

#include<stdio.h>int main()
{
    long long int cnt = 0,k;int n,t,i,j;int a[100005];while(scanf("%d",&n) != EOF){
    scanf("%lld",&k);cnt = 0;for(i=0;i<n;++i)scanf("%d",&a[i]);for(i=0;i<n-1;++i)for(j=i+1;j<n;++j)if(a[i]>a[j])++cnt;if(cnt > k)cnt -= k;elsecnt = 0;printf("%lld\n",cnt);}return 0;
}

运算结果

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4911