hdu 4911 归并求逆序对对数（Java实现）

本文主要是介绍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

Problem Description

bobo has a sequence a ₁,a ₂,…,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 ⁵,0≤k≤10 ⁹). The second line contains n integers a ₁,a ₂,…,a _n (0≤a _i≤10 ⁹).

Output

For each tests:

A single integer denotes the minimum number of inversions.

Sample Input

Sample Output 
 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实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！