hdu-1394（暴力 / 线段树）

77 阅读 0 评论 51 点赞

我是靠谱客的博主落寞大地，最近开发中收集的这篇文章主要介绍hdu-1394（暴力 / 线段树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意：

　　输入一个整数n，接下来随意顺序输入0到n-1之间的数，然后你可以将每一串这样的数的第一个数移到最后一位去，形成新的数字串。要求你输出这样的操作得到的不同数字串中逆序数的最小个数。

思路：

　　首先需要了解一下什么是逆序数，逆序数就是与标准列顺序相反的数。比如标准列是：1 2 3 4 5。那么5 4 3 2 1这个数字串中，4前面有一个5，而这个5本应该出现在4的后面，所以此处逆序数记为1个，依此类推，3处的逆序数记为2……这个数字串的逆序数总和就是1+2+3+4=10。

　　然后再来看这题，这题是问你所有的可以形成的序列中，逆序数总和最小的个数。其实只要我们求出了给定的第一个序列中逆序数的个数，就可根据第一个数移到最后一位这个操作推出逆序数的变化量。现在我们就来看这个变化量有什么规律。因为序列里的数都是0~n-1的，所以比a[0]大的数总共有n-1-a[0]个；比a[0]小的数总共有a[0]个。那么其实变化量就是增加了n-1-a[0]，减少了a[0]。

　　关于这道题目，其实可以直接暴力，然而做这题目的是为了熟练一下线段树的写法，所以给出两种解法（当然是线段树更加高效咯）

代码：

　　暴力

 1 #include<stdio.h>
 2 int a[5010];
 3 const int INF = 0x3f3f3f3f;
 4 int main()
 5 {
 6     int n;
 7     while(scanf("%d", &n) != EOF)
 8     {
 9         int minn = INF;        //首先设定最小值为INF
10         for(int i = 0; i < n; i++)
11         {
12             scanf("%d", &a[i]);
13         }
14         int count = 0;    //用于计算逆序数个数
15         for(int i = 0; i < n; i++)
16         {
17             for(int j = i + 1; j < n; j++)
18             {
19                 if(a[i] > a[j])
20                 {
21                     count++;
22                 }
23             }
24         }
25         minn = count;
26         for(int i = 0; i < n; i++)    //依次后移找其中最小的minn
27         {
28             count = count + n - 2 * a[i] - 1;
29             if(minn > count)
30             {
31                 minn = count;
32             }
33         }
34         printf("%dn", minn);
35     }
36     return 0;
37 }

　　线段树

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int maxn = 5010;
 5 int num[maxn * 4];
 6 int a[maxn];
 7 
 8 void build(int l, int r, int rt)
 9 {
10     num[rt] = 0;    //初始化为0
11     if(l == r)
12         return;
13     int m = (l + r) / 2;
14     build(l, m, rt * 2);
15     build(m + 1, r, rt * 2 + 1);
16 }
17 void update(int pos, int l, int r, int rt)
18 {
19     if(l == r)
20     {
21         num[rt]++;
22         return;
23     }
24     int m = (l + r) / 2;
25     if(pos <= m)
26         update(pos, l, m, rt * 2);
27     else
28         update(pos, m + 1, r, rt * 2 + 1);
29     num[rt] = num[rt * 2] + num[rt * 2 + 1];
30 }
31 int query(int ll, int rr, int l, int r, int rt)
32 {
33     if(ll <= l && rr >= r)
34         return num[rt];
35     int m = (l + r) / 2;
36     int sum = 0;
37     if(ll <= m)
38         sum += query(ll, rr, l, m, rt * 2);
39     if(rr > m)
40         sum += query(ll, rr, m + 1, r, rt * 2 + 1);
41     return sum;
42 }
43 int main()
44 {
45     int n;
46     while(scanf("%d", &n) != EOF)
47     {
48         int count = 0;
49         build(1, n, 1);    //初始化为0，num[1~n]=0
50         for(int i = 0; i < n; i++)
51         {
52             scanf("%d", &a[i]);
53             count += query(a[i] + 1, n, 1, n, 1);
54             //query(a[i] + 1, n, 1, n, 1)这个操作是找在区间a[i]+1到n的数有多少个
55             //也就是说统计之前的数里面有多少个比a[i]要大的数，即逆序数个数
56             update(a[i] + 1, 1, n, 1);
57             //每输入数据update一次，数是0~n-1，但是树上的下标是1~n
58         }
59         int minn = count;
60         for(int i = 0; i < n; i++)
61         {
62             count += (n - 2 * a[i] - 1);
63             minn = min(count, minn);
64         }
65         printf("%dn", minn);
66     }
67     return 0;
68 }