2299:Ultra-QuickSort ( 树状数组 求逆序对 )

el/2024/3/2 11:39:51

题目来源:http://bailian.openjudge.cn/practice/2299?lang=en_US

Ultra-QuickSort

  • 查看
  • 提交
  • 统计
  • 提示
  • 提问

总时间限制: 

7000ms

 

内存限制: 

65536kB

描述

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 

9 1 0 5 4 ,


Ultra-QuickSort produces the output 

0 1 4 5 9 .


Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

输入

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

输出

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

样例输入

5
9
1
0
5
4
3
1
2
3
0

样例输出

6
0

裸的一个树状数组题

关于树状数组 : https://blog.csdn.net/qq_41431457/article/details/88945833

#include<bits/stdc++.h>
using namespace std;
using lom = long long;const int M = 500005;
int a[M], b[M], t[M], n;int lowbit(int x)
{return x & -x;
}int add(int x)//把包含这个数的结点都更新 
{while(x <= n)//范围 {t[x]++;x += lowbit(x);}
}int sum(int x)//查询1~X有几个数加进去了 
{int res = 0;while(x >= 1){	res +=t [x];x -= lowbit(x);}return res;
}bool cmp(int x, int y)
{if(a[x] == a[y]) return x > y;return a[x] > a[y];
}int main()
{while(cin >> n && n){memset(t, 0, sizeof t);lom ans = 0;for(int i = 1; i <= n; i++){scanf("%d", a + i);b[i] = i;}sort(b + 1, b + n + 1, cmp);for(int i = 1; i <= n; i++){add(b[i]);ans += sum(b[i] - 1);}cout << ans << endl;}return 0;
}

归并排序版:

#include<bits/stdc++.h>
#define M 500005
using namespace std;
int a[M],t[M],n;
long long ans=0;
void msort(int l,int r)
{if(l==r) return ;int mid=l+r>>1;msort(l,mid);	msort(mid+1,r);int i=l, j=mid+1, k=l;while(i<=mid&&j<=r)if(a[i]<=a[j]) t[k++]=a[i++];else t[k++]=a[j++], ans+=mid-i+1;while(i<=mid) t[k++]=a[i++];while(j<=r)   t[k++]=a[j++];for(int i=l;i<=r;i++) a[i]=t[i];
}
int main()
{
//	freopen("in.txt","r",stdin);while(cin>>n && n){ans = 0;for(int i=1;i<=n;i++) cin>>a[i];msort(1,n);	cout << ans << endl;}return 0;
}

 


http://www.ngui.cc/el/3419464.html

相关文章

SCU 4437 Carries (思维)

题目地址&#xff1a;http://acm.scu.edu.cn/soj/problem.action?id4437 Carries frog has nn integers a1,a2,…,ana1,a2,…,an, and she wants to add them pairwise. Unfortunately, frog is somehow afraid of carries (进位). She defines hardness h(x,y)h(x,y)for a…

SCU4438 Censor(字符串哈希)

http://acm.scu.edu.cn/soj/problem.action?id4438 Censor frog is now a editor to censor so-called sensitive words (敏感词). She has a long text pp. Her job is relatively simple -- just to find the first occurence of sensitive word ww and remove it. frog…

hdu 1166 敌兵布阵 ( 线段树)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 151658 Accepted Submission(s): 62898 Problem Description C国的死对头A国这段时间正在进行军事演习&#xff0c;所以C国间谍头子Derek和他手下Ti…

NBUT 1723 有多少三元组 (思维)

https://ac.2333.moe/Problem/view.xhtml?id1723 有三个数组A&#xff0c;B&#xff0c;C&#xff0c;每个数组中有n个数&#xff0c;你可以从每个数组中找一个数&#xff0c;使得Ai<Bj<Ck ,(1<I,j,k<n)(1<n<100000,1<Ai,Bj,Ck<1000000)&#xff0c;…

NBUT 1746 可怕的班主任(思维)

https://vjudge.net/problem/2082745/origin 在学校里&#xff0c;一个班由n名学生组成。 在上午晨跑之前&#xff0c;同学们在班主任面前排成一条直线。 班主任对同学们的对齐方式不满意; 确实&#xff0c;同学们按照他们的学号顺序排列&#xff1a;1,2,3&#xff0c;......&…

NBUT 1749 论WC串的唯一性(思维)

https://ac.2333.moe/Problem/view.xhtml?id1749 wc 在爬塔时遇到了一串神秘字符&#xff0c;隐隐之中有一股力量从中透出 wc 很快发现了玄机&#xff0c;这个字符串中每一个含有“wc”的连续子序列都能为wc提供魔法值 找出字符串能为wc提供多少魔法值 注意如果某个连续子…

hud 5690 All X (快速幂 or 循环节)

https://vjudge.net/problem/387912/origin F(x,m)F(x,m) 代表一个全是由数字xx组成的mm位数字。请计算&#xff0c;以下式子是否成立&#xff1a; F(x,m) mod k ≡ cF(x,m) mod k ≡ c Input 第一行一个整数TT&#xff0c;表示TT组数据。 每组测试数据占一行&#xff0c;…

hdu 5694 BD String (递推)

http://acm.hdu.edu.cn/showproblem.php?pid5694 众所周知&#xff0c;度度熊喜欢的字符只有两个&#xff1a;B和D。 今天&#xff0c;它发明了一种用B和D组成字符串的规则&#xff1a; S(1)BS(1)B S(2)BBDS(2)BBD S(3)BBDBBDDS(3)BBDBBDD … S(n)S(n−1)Breverse(flip…

hdu 5695 Gym Class (拓扑排序)

https://vjudge.net/problem/387991/origin 众所周知&#xff0c;度度熊喜欢各类体育活动。 今天&#xff0c;它终于当上了梦寐以求的体育课老师。第一次课上&#xff0c;它发现一个有趣的事情。在上课之前&#xff0c;所有同学要排成一列&#xff0c; 假设最开始每个人有一个…

hud 5689 瞬间移动(组合数+逆元)

http://acm.hdu.edu.cn/showproblem.php?pid5698 有一个无限大的矩形&#xff0c;初始时你在左上角&#xff08;即第一行第一列&#xff09;&#xff0c;每次你都可以选择一个右下方格子&#xff0c;并瞬移过去&#xff08;如从下图中的红色格子能直接瞬移到蓝色格子&#xf…