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
 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 int main()
 5 {
 6     int N;
 7     cin >> N;
 8     static int ci = 1;
 9     while (N)
10     {
11         int M;
12         cin >> M;
13         vector<int> vet(M);
14         for (int i = 0; i < M; i++)
15         {
16             cin >> vet[i];
17         }
18         int count = 0;
19         for (int i = 0; i<M - 1; i++)
20         {
21             for (int j = M - 1; j >i; j--)
22             {
23                 if (vet[j] < vet[j - 1])
24                 {
25                     swap(vet[j], vet[j - 1]);
26                     count++;
27                 }
28             }
29         }
30
31         cout << "Scenario #" << ci << ":" << endl;
32         cout<<count << endl;
33         cout << endl;
34         ci++;
35         N--;
36     }
37 system("pause");
38     return 0;
39 }
时间: 06-21

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

归并排序求逆序数(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 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

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

POJ 1804

题目:http://poj.org/problem?id=1804 大意:给你一串数字,排序.求出最少的交换次数  \ 我用归并做的 #include<iostream> #include<cstring> using namespace std; int aa[500010],bb[500010]; long long s=0; void merge(int l,int m,int r) { int i=l,j=m+1,t=0; while(i<=m&&j&

poj 1084 Brainman

题目链接:http://poj.org/problem?id=1804 思路: 序列的逆序数即为交换次数,所以求出该序列的逆序数即可. 根据分治法思想,序列分为两个大小相等的两部分,分别求子序列的逆序数:对于右子序列中的每一个数,求出左序列中大于它的数的数目,计算的和即为解. 另外,使用Merge排序时,可以很容易求得对于右子序列中的每一个数,左序列中大于它的数的数目. 代码: #include <stdio.h> #include <limits.h> long long Cou

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