首页 > 代码库 > HDU4911-Inversion(树状数组)
HDU4911-Inversion(树状数组)
Inversion
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 914 Accepted Submission(s): 380
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
题意:n个数,最多有k次相邻位置的数的交换,问最小的逆序数为多少
思路:保证每次交换逆序数都减小,可以参考冒泡排序的做法。最后只要计算原数列逆序数,然后减掉k即可。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> #include <map> using namespace std; const int maxn = 100000+10; int sum[maxn]; int n,k; int num[maxn],tn[maxn]; map<int,int> mma; bool cmp(int a,int b){ return a > b; } int lowbit(int x){ return x&(-x); } void add(int x,int d){ while(x < maxn){ sum[x] += d; x += lowbit(x); } } int getS(int x){ int ret = 0; while(x > 0){ ret += sum[x]; x -= lowbit(x); } return ret; } int main(){ while(~scanf("%d%d",&n,&k)){ mma.clear(); memset(sum,0,sizeof sum); for(int i = 1; i <= n; i++){ scanf("%d",&num[i]); tn[i] = num[i]; } sort(tn+1,tn+n+1,cmp); int i = 1,cnt = 1; while(i <= n){ mma[tn[i]] = cnt; int j = i+1; while(j <= n && tn[i]==tn[j]){ j++; } cnt++; i = j; } long long ret = 0; for(int i = 1; i <= n; i++){ ret += getS(mma[num[i]]-1); add(mma[num[i]],1); } long long ans = ret-k; if(ans < 0) ans = 0; cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。