POJ 2299 Ultra-QuickSort（树状数组+离散化+求逆序数）-程序员宅基地

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.
Input
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.
Output
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.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
题意就是输入一个n，接着输入n个数，然后求出这n个数的逆序数。

最简单的求逆序数就是用冒泡排序，每次比较，如果交换说明整两个数是逆序的，ans++，也就是说冒泡排序交换次数就是逆序数；但是时间复杂度是O(n^2).
再就是可以用归并排序来求逆序数，隐隐约约记得之前做过一道题是可以的来求的，虽然现在忘了啊。
这里用树状数组来求。

先说离散化
如果数据量少，但是数据范围大，那么开数组的话会浪费很大一部分空间，所以需要离散化处理(通俗点就是把离散较大的数据紧凑起来)

for (int i=1; i<=n; i++){
    
	scanf("%d", &init[i].val);
	init[i].order=i;
}
sort(init+1, init+n+1, cmp);
for (int i=1; i<=n; i++)
	a[init[i].order]=i;

这样最后a数组的下标就是原来数据的元素的order位置，值就是被处理后的值。从而做到把离散的数据紧凑起来，节省空间。
这样就是把9 1 0 5 4变成5 2 1 4 3
再说求逆序数
这里用树状数组来求，就是每个元素的前面比它大的数量的和就是最终的逆序数。

在说明一点，i-sum(a[i])是本来一共有i个数，sum(a[i])是所有小于等于a[i]的个数，相减就是大于a[i]的个数，也就是在新的数前面大于它的元素的个数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int a[500005];
int c[500005];
struct node{
    
	int order;
	int val;
}init[500005];
int cmp(node a, node b){
    
	return a.val<b.val;
}
int lowbit(int x){
    
	return x&(-x);
}
void update(int index, int val){
    
	while (index<=n){
    
		c[index]+=val;
		index+=lowbit(index);
	}
}
int sum(int index){
    
	int ans=0;
	while (index>=1){
    
		ans+=c[index];
		index-=lowbit(index);
	}
	return ans;
}
int main(){
    
	while (scanf("%d", &n) && n){
    
		for (int i=1; i<=n; i++){
    
			scanf("%d", &init[i].val);
			init[i].order=i;
		}
		sort(init+1, init+n+1, cmp);
		for (int i=1; i<=n; i++)
			a[init[i].order]=i;
		memset(c, 0, sizeof(c));
		long long ans=0;
		for (int i=1; i<=n; i++){
    
			update(a[i], 1);
			ans+=(i-sum(a[i]));
		}
		printf("%lld\n", ans);
	}
	return 0;
}

本文链接：https://blog.csdn.net/weixin_42172261/article/details/98473133

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

react学习总结6--构建工具Gulp、Browserify（二）_react gulp-程序员宅基地

文章浏览阅读1k次。react 学习总结–构建工具Gulp、Browserify（二）1.html 文件处理gulp-htmlmin 插件用于压缩html，可以进行配置，下边是配置信息（选填） var gulp = require('gulp'), htmlmin = require('gulp-htmlmin'); gulp.task('htmlmin', function ()_react gulp

开关电源输入：共模电感，X电容，Y电容，差摸电感理论计算！_共模电感和y电容在滤波方面的区别-程序员宅基地

文章浏览阅读7.6k次，点赞3次，收藏69次。转自：https://mp.weixin.qq.com/s/qp_DSBGKdjNo2-lO2s5v7Q引言在开关电源中，EMI滤波器对共模和差模传导噪声的抑制起着显著的作用。在研究滤波器原理的基础上，探讨了一种对共模、差模信号进行独立分析，分别建模的方法，最后基于此提出了一种EMI滤波器的设计程序。高频开关电源由于其在体积、重量、功率密度、效率等方面的诸多优点，已经被广泛地应用于工业..._共模电感和y电容在滤波方面的区别

IntelliJ IDEA 设置注释模板（Mac）_mac idea 设置注解格式-程序员宅基地

文章浏览阅读7.9k次。类注释模板设置：点击 preferences ，搜索 File and Code Template ,在 Files tab 页下，选择 Class，在类名上面添加模板：/** * @program ${PROJECT_NAME} * @description: ${TODO} * @author: ${USER} * @create: ${YEAR}/${MONTH}/${DAY}..._mac idea 设置注解格式

sizeof用法 _sizeof(4.0+2)-程序员宅基地

文章浏览阅读2k次。Sizeof用法本文主要包括二个部分，第一部分重点介绍在VC中，怎么样采用sizeof来求结构的大小，以及容易出现的问题，并给出解决问题的方法，第二部分总结出VC中sizeof的主要用法。1、 sizeof应用在结构上的情况请看下面的结构：struct MyStruct{double dda1;char dda;int type};对结构MyStruct采用_sizeof(4.0+2)

阅读小结：Large-Margin Softmax Loss for Convolutional Neural Networks_large-margin softmax loss的代码-程序员宅基地

文章浏览阅读2.2k次，点赞3次，收藏4次。徐博最近一直在看我博客，肯定是想看我什么时候不更新，然后好嘲笑我。当然，不排除徐博已经爱上我的可能。What：改进SoftmaxLoss，显式的控制类内的距离，（不让已经对的样本score太高，影响训练）可以防止过拟合。回顾SoftmaxLoss：1. Softmax 就是一个把一个向量归一的函数，输出也是向量。在matlab里就3行代码：% X_large-margin softmax loss的代码

后端java解析复杂嵌套json_java 解析复杂类型的json-程序员宅基地

文章浏览阅读6.2k次。其实不是很复杂百度翻译传过来的json数据：{"from":"zh","to":"en","trans_result":[{"src":"高度600米","dst":"Height 600 meters"}]}现在要取出dst对应的值：Height 600 meters String date="{"from":"zh","to":"en","trans_result":[_java 解析复杂类型的json