首页 > 代码库 > hdu1394

hdu1394

2024-07-17 16:28:03   212人阅读

  题意：给你n个数的序列，每次只允许把最前面的数放到序列后面，求这当中最少的逆序数。（表达能力略差呀，不知道说清没。::>_<::）

  思路：首先是要求原始序列的逆序数，其次再在n次重新排列中，找出逆序数最小的case。

          在求原始序列的逆序数中，如果按照暴力来做，复杂度为n^2，这样用到线段树可以优化为logn；在n次重新排列里找逆序数最小的case就没办法优化啦~~~

          枚举n个数移到序列后面结果的逆序数，然后找最小的就可以了。

  AC代码：（参考大神的Orz）

 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 #include <algorithm> 6  7 using namespace std; 8  9 const int maxn = 50000 + 10;10 int a[maxn];11 12 struct node13 {14     int l, r, v;15 16 } sum[maxn<<2];17 18 void build(int l, int r, int i)19 {20     sum[i].l = l;21     sum[i].r = r;22     if(l == r ) {23         sum[i].v = 0;24         return ;25     }26     int m = (l + r) / 2;27     build(l, m, i<<1);28     build(m+1, r, i<<1|1);29     sum[i].v = sum[i<<1].v + sum[i<<1|1].v;30 }31 32 void Update(int id, int num, int i)33 {34     if(sum[i].l == sum[i].r) {35         sum[i].v = 1;36         return ;37     }38     else {39         if(id <= sum[i<<1].r) Update(id, num, i<<1);40         else Update(id, num, i<<1|1);41     }42     sum[i].v = sum[i<<1].v + sum[i<<1|1].v;43 }44 45 int Query(int l, int r, int i)46 {47     if(sum[i].l == l && sum[i].r == r) {48         return sum[i].v;49     }50     int m = (sum[i].l + sum[i].r) / 2;51     if(r <= m) return Query(l, r, i<<1);52     else if(l > m) return Query(l, r, i<<1|1);53     else return Query(l, m, i<<1) + Query(m+1, r, i<<1|1);54 }55 int main()56 {57     int n;58     while(scanf("%d", &n) != EOF) {59         int num = 0;60         build(0, n-1, 1);61         for(int i = 0; i < n; i++) {62             scanf("%d", &a[i]);63             num += Query(a[i], n-1, 1);64             Update(a[i], n-1, 1);65         }66         int ans = num;67         for(int i = 0; i < n; i++) {68             num = num - a[i] + n -1 - a[i];69             ans = min(ans, num);70         }71         printf("%d\n", ans);72     }73     return 0;74 }
View Code

 


联系
我们