首页 > 代码库 > HDU 4911 http://acm.hdu.edu.cn/showproblem.php?pid=4911(线段树求逆序对）

HDU 4911 http://acm.hdu.edu.cn/showproblem.php?pid=4911(线段树求逆序对）

2024-07-16 02:55:53   214人阅读

题目链接：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 }
View Code

 


联系
我们