首页 > 代码库 > HDU 4911 Inversion(归并排序求逆序数)
HDU 4911 Inversion(归并排序求逆序数)
归并排序求逆序数,然后ans-k与0取一个最大值就可以了。
也可以用树状数组做,比赛的时候可能姿势不对,树状数组wa了、、
Inversion
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 578 Accepted Submission(s): 249
Problem Description
bobo has a sequence a1,a2,…,an. 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 ai>aj.
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 ai>aj.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
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
#include <algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <iomanip> #include <stdio.h> #include <string> #include <queue> #include <cmath> #include <stack> #include <map> #include <set> #define eps 1e-12 ///#define M 1000100 #define LL __int64 ///#define LL long long ///#define INF 0x7ffffff #define INF 0x3f3f3f3f #define PI 3.1415926535898 #define zero(x) ((fabs(x)<eps)?0:x) using namespace std; const int maxn = 10010000; int num[maxn]; LL ans; int tmp[maxn]; void Sell(int l, int mid, int r) { int i = l; int j = mid+1; int k = 0; while(i <= mid && j <= r) { if(num[i] > num[j]) { tmp[k++] = num[j++]; ans += mid-i+1; } else tmp[k++] = num[i++]; } while(i <= mid) tmp[k++] = num[i++]; while(j <= r) tmp[k++] = num[j++]; for(int i = 0; i < k; i++) num[i+l] = tmp[i]; } void Sort(int l, int r) { if(l < r) { int mid = (l+r)/2; Sort(l, mid); Sort(mid+1, r); Sell(l, mid, r); } } int main() { int n, k; while(cin >>n>>k) { ans = 0; for(int i = 0;i < n; i++) scanf("%d",&num[i]); Sort(0, n-1); cout<<max(0LL, ans-k)<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。