浙江财经大学
信息管理与工程学院

HDU 4911 Inversion

本文由 Ocrosoft 于 2016-08-25 21:17:32 发表

Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%I64d & %I64u

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.

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 1

Sample Output

1
2

Solution

题意:交换两个相邻的数不超过k次,求交换后的最小逆序对数。
思路:(定理)如果逆序数大于0,那么必定存在1<=i<n使得i和i+1交换后逆序数减1。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX / 2;
const int MAXN = 100000 + 10;
using namespace std;
//逆序对模板
int a[100005];
int le[100005], ri[100005];
ll cnt;
void merge(int* a, int p, int q, int r)
{
	int i, j, k, n1, n2;
	n1 = q - p + 1;
	n2 = r - q;
	for (i = 0; i < n1; i++)
	{
		le[i] = a[p + i];
	}
	for (i = 0; i < n2; i++)
	{
		ri[i] = a[q + i + 1];
	}
	le[n1] = ri[n2] = 0x7fffffff;

	i = j = 0;
	for (k = p; k <= r; k++)
	{
		if (le[i] <= ri[j])
		{
			a[k] = le[i];
			i++;
		}
		else
		{
			a[k] = ri[j];
			j++;
			cnt += n1 - i;
		}
	}
	return;
}
void mergesort(int* a, int p, int r)
{
	int q;
	if (p < r)
	{
		q = (p + r) / 2;
		mergesort(a, p, q);
		mergesort(a, q + 1, r);
		merge(a, p, q, r);
	}
	return;
}
int main()
{
	int n, k;
	while (cin >> n >> k)
	{
		cnt = 0;
		for (int i = 0; i < n; i++)scanf("%d", &a[i]);
		mergesort(a, 0, n - 1);
		//如果逆序数大于0,那么必定存在1 <= i<n使得i和i + 1交换后逆序数减1
		printf("%I64d\n", max(cnt - k, (ll)0));
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » HDU 4911 Inversion

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址