POJ 1804 Brainman(归并排序)

传送门

Description

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 
Here‘s 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 Raymond‘s 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. Rest assured he will pay a very good prize for it.

Input

The first line contains the number of scenarios. 
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

Output

Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.

Sample Input

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

Sample Output

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

思路

最小相邻交换次数=逆序数

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int maxn = 1005;
int sum = 0;
void merge_array(int array[],int left,int mid,int right)
{
	if (left >= right)	return;
	int i = left,j = mid + 1,k = 0;
	int *p;
	p = (int *)malloc((right-left+1)*sizeof(int));
	while (i <= mid && j <= right)
	{
		if (array[i] <= array[j])	p[k++] = array[i++];
		else	p[k++] = array[j++],sum += mid - i + 1;       //[i,mid]都能与array[j]形成逆序数
	}
	while (i <= mid)	p[k++] = array[i++];
	while (j <= right)	p[k++] = array[j++];
	for (i = 0;i < k;i++)	array[i+left] = p[i];
	free(p);
}

void merge_sort(int array[],int left,int right)
{
	if (left >= right)	return;
	int mid = left + ((right - left)>>1);
	merge_sort(array,left,mid);
	merge_sort(array,mid+1,right);
	merge_array(array,left,mid,right);
}

int main()
{
	int T,Case = 0;
	scanf("%d",&T);
	while (T--)
	{
		int N,a[maxn];
		scanf("%d",&N);
		for (int i = 0;i < N;i++)	scanf("%d",&a[i]);
		sum = 0;
		merge_sort(a,0,N-1);
		printf("Scenario #%d:\n%d\n\n",++Case,sum);
	}
	return 0;
}

  

时间: 10-08

POJ 1804 Brainman(归并排序)的相关文章

POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

Brainman Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 10575   Accepted: 5489 Description BackgroundRaymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just b

POJ 1804 Brainman

Description 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 c

归并排序求逆序数(POJ 1804,POJ 2299,HDU 4911)

首先,明确两个概念: 逆序对:数列a[1],a[2],a[3]-中的任意两个数a[i],a[j] (i<j),如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对. 逆序数:一个数列中逆序对的总数. 例题一:POJ 1804.   点击打开链接 解题思路:每次交换只能减少一个逆序,而且必定能减少一个逆序,从而问题就转换为求逆序个数了.这题数据规模很小,暴力可过. 我这里提供了用Merge_sort的方法求解逆序数,时间复杂度为O(nlogn). 关于归并排序:归并排序是将数列a[l,h

POJ 2299 Ultra-QuickSort(归并排序求逆序对数)

题目地址:POJ 2299 今天下午的多校看来没有白做...实在做不出题闲着无聊看小白鼠学会了个归并排序.哈哈. 归并排序简单地说其实就是先分成一个二叉树直至单个,然后依次从最底层不断进行合并,逆序对数就是在合并的过程中,加入后面的那段中到了比他大的时候,那后面的那些就都是比他大的,都是逆序对数,所以直接加上即可.网上资料很多,就不细说了..用了分治的思想. 自己根据理解写的代码,考虑的太不全面了..又调了好长时间... 代码如下: #include <algorithm> #include

POJ训练计划2299_Ultra-QuickSort(归并排序求逆序数)

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 39279   Accepted: 14163 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swappin

POJ 1804 Eqs

C - Eqs Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Description Consider equations having the following form: a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0 The coefficients are given integers from the interval [-5

POJ 1804 逆序对数量 / 归并排序

Brainman Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 12175   Accepted: 6147 Description Background Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just

B - Brainman (POJ - 1804)

- 题目大意 给出一串数字,问能是它为顺序排列的最小交换数字方式. - 解答思路 利用归并排序来求逆序数(注意数组的大小就行了). - 代码 #include<iostream> using namespace std; int num[100000]; int main() { int n,m; cin >> n; for (int i = 1; i <= n; i++) { cin >> m; for (int j = 1; j <= m; j++) c

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