HDU 5775:Bubble Sort(树状数组)

http://acm.hdu.edu.cn/showproblem.php?pid=5775

Bubble Sort

Problem Description

P is a permutation of the integers from 1 to N(index starting from 1).
Here is the code of Bubble Sort in C++.

for(int i=1;i<=N;++i)    for(int j=N,t;j>i;—j)        if(P[j-1] > P[j])            t=P[j],P[j]=P[j-1],P[j-1]=t;

After the sort, the array is in increasing order. ?? wants to know the absolute values of difference of rightmost place and leftmost place for every number it reached.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each consists of one line with one integer N, followed by another line with a permutation of the integers from 1 to N, inclusive.

limits

T <= 20
1 <= N <= 100000
N is larger than 10000 in only one case.

Output

For each test case output “Case #x: y1 y2 … yN” (without quotes), where x is the test case number (starting from 1), and yi is the difference of rightmost place and leftmost place of number i.

Sample Input

2

3

3 1 2

3

1 2 3

Sample Output

Case #1: 1 1 2

Case #2: 0 0 0

Hint

In first case, (3, 1, 2) -> (3, 1, 2) -> (1, 3, 2) -> (1, 2, 3) the leftmost place and rightmost place of 1 is 1 and 2, 2 is 2 and 3, 3 is 1 and 3 In second case, the array has already in increasing order. So the answer of every number is 0.

题意:求出1-n里面各个数在冒泡排序里面可以达到的最右距离和最左距离之差是多少。

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <cmath>
 6 using namespace std;
 7 #define N 100005
 8 /*
 9 树状数组
10 从右边往左扫看右边有多少个数是小于当前位置的数的,
11 然后可以达到的最右距离就是最初始的位置加上小于它的数的数量
12 可以达到的最左距离是min(最初始的位置,i)
13 所以最右减去最左就是i的答案了.
14 */
15 int bit[N];
16 int num[N], tmp[N], r[N];
17
18 int lowbit(int x)
19 {
20     return x & (-x);
21 }
22
23 void update(int x)
24 {
25     while(x <= N) {
26         bit[x] += 1;
27         x += lowbit(x);
28     }
29 }
30
31 int query(int x)
32 {
33     int ans = 0;
34     while(x) {
35         ans += bit[x];
36         x -= lowbit(x);
37     }
38     return ans;
39 }
40
41 int main()
42 {
43     int t;
44     scanf("%d", &t);
45     for(int cas = 1; cas <= t; cas++) {
46         memset(bit, 0, sizeof(bit));
47         int n;
48         scanf("%d", &n);
49         for(int i = 1; i <= n; i++){
50             scanf("%d", num+i);
51             tmp[num[i]] = i;
52         }
53         for(int i = n; i > 0; i--) {
54             update(num[i]);
55             r[num[i]] = query(num[i] - 1);
56         }
57
58         printf("Case #%d: ", cas);
59         for(int i = 1; i <= n; i++) {
60             if(i != n) printf("%d ", abs(tmp[i]+r[i] - min(tmp[i], i)));
61             else printf("%d\n", abs(tmp[i]+r[i] - min(tmp[i], i)));
62         }
63     }
64     return 0;
65 }
时间: 07-28

HDU 5775:Bubble Sort(树状数组)的相关文章

hdu 5775 Bubble Sort (树状数组)

Bubble Sort Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 591    Accepted Submission(s): 359 Problem Description P is a permutation of the integers from 1 to N(index starting from 1).Here is t

hdu 5775 Bubble Sort 树状数组+冒泡排序

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5775 [题意]按照题目的冒泡排序求每个数在排序过程中到达最右边位置与最左边位置之差. [解题思路]考虑i位置上的数字a[i]在冒泡排序过程的变化情况.a[i]会被其后面比a[i]小的数字各交换一次,之后a[i]就会只向前移动.数组从右向左扫,树状数组维护一下得到每个值右边有多少个比其小的值,加上原位置得到最右位置,最左位置为初始位置和最终位置的最小值. [时间复杂度]O(n lg n)O(n\ lg

HDU 5775 L - Bubble Sort 树状数组

给定一段冒泡排序的代码,要求输出每个数字能到达的最右边的位置和最左边的位置的差 因为那段冒泡排序的代码是每次选取一个最小的数,放在左边的,所以,每个数最多能到达右边的位置应该是起始位置i+右边有多少个数比它大. 它能到达的最左的位置,可以这样考虑 1.它本来应该是排去起始位置的左边的,就是它本来是一个小的数字,起始位置在末尾这种情况的话.最左边的值就是a[i] 2.它是去右边的,那么最左边的值就是起始位置, 两种取max就去可以了 #include <cstdio> #include <

HDU 5775 Bubble Sort(冒泡排序)

HDU 5775 Bubble Sort(冒泡排序) Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)   Problem Description - 题目描述 P is a permutation of the integers from 1 to N(index starting from 1).Here is the code of Bubble Sort in C++.

HDU 3333 Turing Tree 树状数组 离线查询

题意: 给你一个数列,然后有n个查询,问你给定区间中不同数字的和是多少. 思路还是比较难想的,起码对于蒟蒻我来说. 将区间按照先右端点,后左端点从小到大排序之后,对于每个查询,我只要维护每个数字出现的最后一次就可以了(这个结论稍微想一下就可以证明是正确的). 然后就是简单的点更新,区间求和问题了- #include <cstdio> #include <cstring> #include <iostream> #include <map> #include

HDU 1541 Stars (树状数组)

Problem Description Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given

HDU 3854 Glorious Array(树状数组)

题意:给一些结点,每个结点是黑色或白色,并有一个权值.定义两个结点之间的距离为两个结点之间结点的最小权值当两个结点异色时,否则距离为无穷大.给出两种操作,一种是将某个结点改变颜色,另一个操作是询问当前距离小于K的结点有多少对,K是一个定值. 思路:先求最初时候小于k的结点有多少对,然后每次改变颜色的时候,统计该点左侧和右侧各有多少同色和异色的结点(这一步使用树状数组),分别处理就行.另外需要预处理离某个结点最近的两个距离小于K的结点的位置. 代码写的略乱. #include<cstdio> #

HDU 2492 Ping pong (树状数组)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2492 Ping pong Problem Description N(3<=N<=20000) ping pong players live along a west-east street(consider the street as a line segment). Each player has a unique skill rank. To improve their skill rank

HDU 1541 Stars(树状数组)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1541 解析: 题意:大概就是计算每颗星星左下边包括了多少颗星星,这个数值就是level.左下边不包括本身,不超过本身的x,y的坐标,可以等于.问每种level有多少颗星星. 这题,一开始想不到怎么用到树状数组,后来看了一下,发现题目给的数据是已经按x,y排好序的,所以我们可以不用管y的值. 注意: 1.每次输入一个坐标对之后,都要计算一下这个它的level. 2.此题的x坐标可以为0,而树状数组是从

HDU 1892 二维树状数组

See you~ Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 3485    Accepted Submission(s): 1103 Problem Description Now I am leaving hust acm. In the past two and half years, I learned so many kno