本文主要是介绍hdu 4911 归并 求逆序对对数（Java实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
网页链接
Inversion
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1962 Accepted Submission(s): 765
Total Submission(s): 1962 Accepted Submission(s): 765
Problem Description
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.
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).
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.
A single integer denotes the minimum number of inversions.
Sample Input
3 1 2 2 1 3 0 2 2 1
Sample Output
1
2
1
2
import java.util.Scanner;
public class Main
{
static int arr[] = new int[100005];
static int temp[] = new int[100005];
static int n,k;
static long ans;
static void merge(int start, int mid, int end)
{
int i = start, j = mid +1;
int cnt = 0;
while(i <= mid && j <= end)
{
if(arr[i] > arr[j])
{
temp[cnt++] = arr[j++];
ans += (mid-i+1);
}
else
{
temp[cnt++] = arr[i++];
}
}
while(i <= mid)
{
temp[cnt++] = arr[i++];
}
while(j <= end)
{
temp[cnt++] = arr[j++];
}
cnt = 0;
for(int tmp = start; tmp <= end;)
{
arr[tmp++] = temp[cnt++];
}
}
static void mergeSort(int start, int end)
{
if(start < end)
{
int mid = (start+end)/2;
mergeSort(start,mid);
mergeSort(mid+1, end);
merge(start,mid,end);
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt())
{
n = sc.nextInt();
k = sc.nextInt();
ans = 0L;
for(int i = 0; i < n; ++i)
arr[i] = sc.nextInt();
mergeSort(0,n-1);
System.out.println(ans-k>=0?ans-k:0);
}
}
}
这篇关于hdu 4911 归并 求逆序对对数（Java实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
