首页 > 代码库 > HDU 4911 http://acm.hdu.edu.cn/showproblem.php?pid=4911(线段树求逆序对)
HDU 4911 http://acm.hdu.edu.cn/showproblem.php?pid=4911(线段树求逆序对)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4911
解题报告: 给出一个长度为n的序列,然后给出一个k,要你求最多做k次相邻的数字交换后,逆序数最少是多少?
因为每次相邻的交换操作最多只能减少一个逆序对,所以最多可以减少k个逆序对,所以我们只要求出原来的序列有多少个逆序对然后减去k再跟0取较大的就可以了。
因为数据范围是10的五次方,所以暴力求肯定会TLE,所以要用n*logn算法求逆序对,n*logn算法有几种可以求逆序对的:
线段树,树状数组,归并排序。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 typedef __int64 INT; 7 const int maxn = 100000+5; 8 9 struct node10 {11 int d,cixu;12 }A[maxn];13 struct Node14 {15 int l,r;16 INT n;17 }tree[4*maxn];18 bool cmp1(node a,node b)19 {20 if(a.d == b.d) return a.cixu < b.cixu;21 return a.d < b.d;22 }23 bool cmp2(node a,node b)24 {25 return a.cixu < b.cixu;26 }27 void build(int p)28 {29 if(tree[p].l == tree[p].r) return ;30 int mid = (tree[p].l + tree[p].r) / 2;31 tree[2*p].l = tree[p].l;32 tree[2*p].r = mid;33 tree[2*p].n = tree[2*p+1].n = 0;34 tree[2*p+1].l = mid + 1;35 tree[2*p+1].r = tree[p].r;36 build(2*p);37 build(2*p+1);38 }39 void insert(int p,int l)40 {41 tree[p].n++;42 if(tree[p].l == tree[p].r) return ;43 int mid = (tree[p].l + tree[p].r) / 2;44 if(l <= mid) insert(2*p,l);45 else insert(2*p+1,l);46 }47 INT query(int p,int l,int r)48 {49 if(l > r) return 0;50 if(tree[p].l == l && tree[p].r == r)51 return tree[p].n;52 int mid = (tree[p].l + tree[p].r) / 2;53 if(r <= mid) query(2*p,l,r);54 else if(l <= mid && r > mid)55 return query(2*p,l,mid) + query(2*p+1,mid+1,r);56 else return query(2*p+1,l,r);57 }58 59 int main()60 {61 int n;62 INT k;63 while(scanf("%d%I64d",&n,&k)!=EOF)64 {65 tree[1].l = 1;66 tree[1].r = n;67 tree[1].n = 0;68 build(1);69 for(int i = 1;i <= n;++i)70 {71 scanf("%d",&A[i].d);72 A[i].cixu = i;73 }74 sort(A+1,A+n+1,cmp1);75 int f = 0,hehe = 0x7fffffff;76 for(int i = 1;i <= n;++i)77 {78 if(A[i].d != hehe)79 {80 hehe = A[i].d;81 f++;82 }83 A[i].d = f;84 }85 sort(A+1,A+n+1,cmp2);86 INT ans = 0;87 for(int i = 1;i <= n;++i)88 {89 ans += query(1,A[i].d+1,n);90 insert(1,A[i].d);91 }92 ans = ans-k > 0? (ans-k) : 0;93 printf("%I64d\n",ans);94 }95 return 0;96 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。