网站备案信息传,无锡网站开发平台,网站建设 套餐,wordpress首页分页函数目录 题目描述 输入样例: 输出样例: 逆序对的含义#xff1a; 具体思路#xff1a; 归并排序#xff1a; 求逆序对#xff1a; 代码实现#xff1a; 对于mid-z1举个例子 题目描述 注意#xff1a;本问题算法的时间复杂度要求为O(nlogn), 否则得分无效 题目来源#xff… 目录 题目描述 输入样例: 输出样例: 逆序对的含义 具体思路 归并排序 求逆序对 代码实现 对于mid-z1举个例子 题目描述 注意本问题算法的时间复杂度要求为O(nlogn), 否则得分无效 题目来源http://poj.org/problem?id1804 Background Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task. Problem Heres what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example: Start with: 2 8 0 3 swap (2 8) 8 2 0 3 swap (2 0) 8 0 2 3 swap (2 3) 8 0 3 2 swap (8 0) 0 8 3 2 swap (8 3) 0 3 8 2 swap (8 2) 0 3 2 8 swap (3 2) 0 2 3 8 swap (3 8) 0 2 8 3 swap (8 3) 0 2 3 8 So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps: Start with: 2 8 0 3 swap (8 0) 2 0 8 3 swap (2 0) 0 2 8 3 swap (8 3) 0 2 3 8 The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymonds mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question in O(nlogn). Rest assured he will pay a very good prize for it. 输入格式: The first line contains the length N (1 N 1000) of the sequence The second line contains the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks. 输出格式: Print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. 输入样例: 在这里给出一组输入。例如 6
-42 23 6 28 -100 65537 输出样例: 在这里给出相应的输出。例如 5 如标题所示题目简单来说就是求一个数组中逆序对的个数 逆序对的含义 对于数列的第 i 个和第 j 个元素如果满足 i j 且 a[i] a[j]则其为一个逆序对 另外一个元素可能存在于多个逆序对中例如 第i个元素第j个元素第k个元素存在ijk且a[i]a[j]a[k]则有两个逆序对且都含有a[i] 以题目为例 -42 23 6 28 -100 65537 从小到大排序为 -100 -42 6 23 28 65537 -100比它左边的-42 23 6 28都小所以逆序对加4 -100与-42为一个逆序对 -100与23为一个逆序对 -100与6为一个逆序对 -100与28为一个逆序对 6比它左边的23小所以逆序对加1 6与23为一个逆序对 415即为答案 具体思路 归并排序 1、将序列平均分为两个区间部分 2、递归排序左区间和右区间 3、将左右两个区间已经排序好的序列合并成一个有序的序列 求逆序对 分为三种情况 假设需要对比的两个元素 1、两个元素都在区间的左边 2、两个元素都在区间的右边 3、两个元素一个在区间左边一个在区间右边 代码实现 #includeiostream
using namespace std;
#define int long long
const int N1e57;
int sz[N];//存储序列
int ans0;
void gb_px(int l,int r)
{if(lr)return;//如果左边的下标大于等于右边代表已经无法分成两部分了所以返回即可int mid(lr)1;//相当于mid(lr)/2;gb_px(l,mid);//进入左区间排序gb_px(mid1,r);//进入右区间排序int zl,ymid1,xb0;int zs[r-l1];//可以用全局变量但是数组长度肯定不超过r-l1while(zmidyr)//左边的起始点不能超过中点右边的起始点不能超过右边的右边的界限{if(sz[z]sz[y])//如果左边的数小于等于右边则将左边的元素放在前面用zs数组暂时存此时左边的下标往右移动一位{zs[xb]sz[z];}else//否则如果右边的数小于左边则将右边的元素放在前面用zs数组暂时存此时右边的下标往右移动一位{zs[xb]sz[y];ansmid-z1;//关键一步此时中点减去左边指针的下标加一即为对于sz[y]这个数实际计算的是在左区间中大于右区间指向的这个数的个数在这个区间中的逆序对的个数。}}//移动完以后还会有剩下的数显然他们已经是有序的了while(zmid)//左半边还剩下几个元素全都加进去{zs[xb]sz[z];}while(yr)//右半边还剩下几个元素全都加进去{zs[xb]sz[y];}for(int il,j0;ir;i,j)//更新l到r的数组元素的顺序因为zs数组是从0开始为下标存储的{sz[i]zs[j];}
}
signed main()
{int n;cinn;for(int i0;in;i){cinsz[i];}gb_px(0,n-1);//进入归并排序数组下标为0到n-1coutans;
} 对于mid-z1举个例子 例如 现在存在一个区间他们的开始下标假设为0此时的mid为07/23即z0mid3y4。 1 2 3 4 2 3 4 5 很明显 可以分成 1 2 3 4为左区间 2 3 4 5为右区间 左区间为上一轮排序好的 右区间也为上一轮排序好的 左区间中1 2小于右区间的2所以将 1 2放入zs数组中存储 此时左区间的3显然大于右区间的2所以此时逆序对的个数为3-212个 为什么是mid-z1呢因为左区间右区间序列是已经排序好的 可以发现3后面的所有元素都是大于右区间中2的即算出了左区间中大于当前右区间指向的这个数2的元素的个数为2个
