POJ 1840 Brainman(逆序对数)

题目链接:http://poj.org/problem?id=1804

题意:给定一个序列a[],每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列.

思路:题目就是要求逆序对数,我们知道,求逆序对最典型的方法就是树状数组,但是还有一种方法就是Merge_sort(),即归并排序。实际上归并排序的交换次数就是这个数组的逆序对个数,归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序,然后再将这两半合并起来。在合并的过程中(设l<=i<=mid,mid+1<=j<=h),当a[i<=a[j]时,并不产生逆序数;当a[i]>a[j]时,在前半部分中比a[i]大的数都比a[j]大,将a[j]放在a[i]前面的话,逆序数要加上mid+1-i。因此,可以在归并排序中的合并过程中计算逆序数。

code:

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4
 5 using namespace std;
 6 const int N = 1005;
 7
 8 int a[N],tmp[N];
 9 int ans;
10
11 void Merge(int l,int m,int r)
12 {
13     int i = l;
14     int j = m + 1;
15     int k = l;
16     while(i <= m && j <= r)
17     {
18         if(a[i] > a[j])
19         {
20             tmp[k++] = a[j++];
21             ans += m - i + 1;
22         }
23         else
24         {
25             tmp[k++] = a[i++];
26         }
27     }
28     while(i <= m) tmp[k++] = a[i++];
29     while(j <= r) tmp[k++] = a[j++];
30     for(int i=l;i<=r;i++)
31         a[i] = tmp[i];
32 }
33
34 void Merge_sort(int l,int r)
35 {
36     if(l < r)
37     {
38         int m = (l + r) >> 1;
39         Merge_sort(l,m);
40         Merge_sort(m+1,r);
41         Merge(l,m,r);
42     }
43 }
44
45 int main()
46 {
47     int n,T,tt=1;
48     scanf("%d",&T);
49     while(T--)
50     {
51         scanf("%d",&n);
52         for(int i=0;i<n;i++)
53             scanf("%d",&a[i]);
54         ans = 0;
55         Merge_sort(0,n-1);
56         printf("Scenario #%d:\n%d\n\n",tt++,ans);
57     }
58     return 0;
59 }
时间: 09-10

POJ 1840 Brainman(逆序对数)的相关文章

分治法 求 逆序对数 的个数 时间复杂度为O(n*logn)

思路: 分治法 归并排序的过程中,有一步是从左右两个数组中,每次都取出小的那个元素放到tmp[]数组中 右边的数组其实就是原数组中位于右侧的元素.当不取左侧的元素而取右侧的元素时,说明左侧剩下的元素均比右侧的第一个元素大,即均能构成一个逆序对.假设现在左侧剩余n个元素,则逆序对数+n. 另外,如果当所有右侧的元素都取完,但是左侧仍然有元素剩余时,左侧剩余的元素已经在之前的运算中加到了逆序对中,不需要再添加一次 下面给出 归并排序 和 求逆序对数 两份代码: code1: 归并排序 #includ

hdu 4911 求逆序对数+树状数组

http://acm.hdu.edu.cn/showproblem.php?pid=4911 给定一个序列,有k次机会交换相邻两个位置的数,问说最后序列的逆序对数最少为多少. 实际上每交换一次能且只能减少一个逆序对,所以问题转换成如何求逆序对数. 归并排序或者树状数组都可搞 树状数组: 先按大小排序后分别标号,然后就变成了求1~n的序列的逆序数,每个分别查询出比他小的用i减,在把他的值插入即可 #include <cstdio> #include <cstdlib> #includ

hdu 5273 Dylans loves sequence(区间逆序对数-莫队算法)

n<=1000,q<=100000,求区间内逆序对数,从[l,r]显然可以log(n)的时间内移动到[l-1,r],[l+1,r],[l,r-1],[l,r+1],那么就可以用莫队进行离线 复杂度大概是O(n*sqrt(n)*log2(n)),不过可以暴力枚举起点,然后向后统计,然后O(1)回答,不过n再大就无法解决了,这个即使是n<=1e5也可以很快得到答案,开-o优化,1e6也可以很快得到答案 #include<bits/stdc++.h> using namespace

【Todo】求逆序对数总结

用归并排序方式 最原始的方法的复杂度是O(n^2). 使用归并排序的方式,可以把复杂度降低到O(nlgn). 设A[1..n]是一个包含N个非负整数的数组.如果在i〈 j的情况下,有A〉A[j],则(i,j)就称为A中的一个逆序对.例如,数组(3,1,4,5,2)的“逆序对”有<3,1>,<3,2><4,2><5,2>,共4个. 注:我觉得方法是在归并过程中,记录每次归并,后面的分组中被放到了前面的元素的个数. 的确是这样的.下面这个也是MergeSort的

利用归并排序法计算一个序列里有多少逆序对数(详细讲解)

前言 今天遇到求逆序对的问题,经过一番思索之后,特意来总结一下.因为也学习到了很多方法,以前自己一些百思不得其解的问题也有了解答. 正文 先上一个简单的问题: 分析:题目中说使用插入排序,也就是在排序过程中计算交换的次数,按照插入排序的原理,先定第一个,再定前两个的顺序,以此类推,只要交换了,我的次数就加一,但实际上,我们一直按照原始序列的顺序一直在往后走,所以(好,重点来了)我们要插入的就是前面比我大的数字前面的位置,也就是说,我需要交换的次数就是前面比我大的数字的个数,那么我考虑那就没必要进

bzoj 3744 Gty的妹子序列 区间逆序对数(在线) 分块

题目链接 题意 给定\(n\)个数,\(q\)个询问,每次询问\([l,r]\)区间内的逆序对数. 强制在线. 思路 参考:http://www.cnblogs.com/candy99/p/6579556.html 离线的话就如上一题bzoj 3289 Mato的文件管理,可以直接用 莫队 搞,在线的话怎么办呢? 分块大法好. 1 预处理出两个信息: \(f[i][j]\):从 第\(i\)块开始位置 到 位置\(j\) 这段区间的逆序对数 \(s[i][j]\):前\(i\)块中\(\leq

一维数组中的任意二元素交换最多只能将整个序列的逆序对数减少1

这是对的,值得思考,毕竟应用不是太少(所以要说服自己,用的时候更有底气). 设一序列\(a_1,a_2,\cdots,a_n\),其中有\(a_i(1\leq i \leq n)\). 假设要通过交换\(a_i\)与某个数的位置来减少逆序对的数量. 交换的对象分这么几类: 1.\(a_i\)后面比\(a_i\)小的数 2.\(a_i\)后面比\(a_i\)大的数 3.\(a_i\)前面比\(a_i\)小的数 4.\(a_i\)前面比\(a_i\)大的数 假设交换的对象是\(a_j\) 前置说明(

(c) hdu1394* (求逆序对数)(线段树)

(c) hdu1394 如在阅读本文时遇到不懂的部分,请在评论区询问,或跳转 线段树总介绍 线段树求逆序对数比较少见啊(归并排序多快啊...但是本文是讲解线段树写法...),何况这题还加了点别的玩意儿... 1. 本来这种题目要离散化的,可是体中保证了数列0~n-1. 2. 每次把首位放到最末,显然不能 每次都求逆序对 ,于是又到了推 倒 导时间. 由 a1 a2 ... an 变为 a2 a3 ... an a1 减少的逆序对数为 a2~an中比a1小的数的个数 增加的逆序对数为 a2~a1中

Ultra-QuickSort POJ - 2299 (逆序对)

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