首页 > 代码库 > hdu 4911 求逆序对数+树状数组
hdu 4911 求逆序对数+树状数组
http://acm.hdu.edu.cn/showproblem.php?pid=4911
给定一个序列,有k次机会交换相邻两个位置的数,问说最后序列的逆序对数最少为多少。
实际上每交换一次能且只能减少一个逆序对,所以问题转换成如何求逆序对数。
归并排序或者树状数组都可搞
树状数组:
先按大小排序后分别标号,然后就变成了求1~n的序列的逆序数,每个分别查询出比他小的用i减,在把他的值插入即可
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define RD(x) scanf("%d",&x) #define RD2(x,y) scanf("%d%d",&x,&y) #define clr0(x) memset(x,0,sizeof(x)) typedef long long LL; typedef pair<int,int> p; const int maxn=100005; LL f[maxn]; int n; void add(int x,LL y) { for(;x<=n;x += x&(-x)) f[x]+=y; } LL sum(int x){ LL s=0; for (;x;x -= x&(-x)) s+=f[x]; return s; } p a[maxn]; int k; bool cmp(p i,p j){ return i.second < j.second; } int main(){ int i; LL s; while (~RD2(n,k)){ for (i=0;i<n;++i){ RD(a[i].first); a[i].second=i; } sort(a,a+n); for (i=0;i<n;++i) a[i].first = i+1; sort(a,a+n,cmp); clr0(f); for (s=i=0;i<n;++i){ s += i - sum(a[i].first); add(a[i].first,1); } printf("%I64d\n",max(0LL,s-k)); } return 0; }
归并排序:
每次归并发现需要前后交换时都给总的ret加上mid - mvl + 1,因为mvl到mid直接的数都比mvr下标上的数大
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <queue> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define RD(x) scanf("%d",&x) #define RD2(x,y) scanf("%d%d",&x,&y) #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define clr0(x) memset(x,0,sizeof(x)) typedef long long LL; const int maxn = 1e5+5; LL k; int n, a[maxn], b[maxn]; LL merge_sort(int l, int r) { if (l == r) return 0; int mid = (l + r) / 2; LL ret = merge_sort(l, mid) + merge_sort(mid+1, r); int mvl = l, mvr = mid+1, mv = l; while (mvl <= mid || mvr <= r) { if (mvr > r || (mvl <= mid && a[mvl] <= a[mvr])) { b[mv++] = a[mvl++]; } else { ret += mid - mvl + 1; b[mv++] = a[mvr++]; } } for (int i = l; i <= r; i++) a[i] = b[i]; return ret; } int main () { while (scanf("%d%I64d", &n, &k) == 2) { for (int i = 1; i <= n; i++) RD(a[i]); printf("%I64d\n", max(merge_sort(1, n) - k, 0LL)); } return 0; }
hdu 4911 求逆序对数+树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。