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

浏览数：24 / 时间：2015年06月09日

题目链接：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 node
10 {
11     int d,cixu;
12 }A[maxn];
13 struct Node
14 {
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 }