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 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题意 两个位置的元素可以任意交换 交换最少的数量使序列有序解析  归并排序求逆序对AC代码
#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn = 1e5+50,inf=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int a[maxn],t[maxn],ans;
void merge_sort(int *a,int x,int y,int *t)
{
    if(y-x>1)
    {
        int m=x+(y-x)/2;    //划分
        int p=x,q=m,i=x;
        merge_sort(a,x,m,t); //递归求解
        merge_sort(a,m,y,t); //递归求解
        while(p<m||q<y)    //只要有一个序列非空就要继续合并
        {

            if(q>=y||( p<m && a[p]<=a[q]))  //当第二个序列为空直接复制 两个都不为空进行比较
                t[i++]=a[p++];
            else
                t[i++]=a[q++],ans+=m-p;
        }
        for(int i=x;i<y;i++)    //将排好序的数组再复制回给a
            a[i]=t[i];
    }
}
int main()
{
    int n,m,kase=1;
    cin>>m;
    while(m--)
    {
        cin>>n;
        ans=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        merge_sort(a,0,n,t);//左闭右开
        printf("Scenario #%d:\n%d\n\n",kase++,ans);
    }
}

归并排序

/*

分治三步法:

    划分问题:把序列分成元素个数尽量相等的两半
    递归求解:把两半元素分别排序
    合并问题:把两个有序表合并成一个
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+50,inf=0x3f3f3f3f;
typedef long long ll;
const int mod=1e9+7;
int a[maxn],t[maxn];
void merge_sort(int *a,int x,int y,int *t)
{
    if(y-x>1)
    {
        int m=x+(y-x)/2;    //划分
        int p=x,q=m,i=x;
        merge_sort(a,x,m,t); //递归求解
        merge_sort(a,m,y,t); //递归求解
        while(p<m||q<y)    //只要有一个序列非空就要继续合并
        {

            if(q>=y||( p<m && a[p]<=a[q]))  //当第二个序列为空直接复制 两个都不为空进行比较
                t[i++]=a[p++];
            else
                t[i++]=a[q++];
        }
        for(int i=x;i<y;i++)    //将排好序的数组再复制回给a
            a[i]=t[i];
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    merge_sort(a,0,n,t);//左闭右开
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

原文地址:https://www.cnblogs.com/stranger-/p/9273046.html

时间: 07-04

POJ 1804 逆序对数量 / 归并排序的相关文章

POJ 2299 逆序对(归并排序)

终于解决了一个忧伤好久的问题,严重拖了项目进度,深感惭愧!一直被一系列的问题所困扰,然后又只能自己一个人摸索,也是一段辛酸忧伤史,现在小结一下上个月在做二维码的过程中所碰到的问题以及解决办法,现在庆幸终于解决好了,终于能将这个功能告一段落,一下小结也是分享一下Unity的某些"坑",让同行少走弯路,起码在二维码这方面应该会有所启迪,欣慰的是接下来几天终于可以做自己应该做的事情了! 效果图: 先小结一下碰到的问题: 1.Unity工程屏幕方向与Android工程屏幕方向要一致的问题 本来

HDU 1394Minimum Inversion Number 数状数组 逆序对数量和

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 18543    Accepted Submission(s): 11246 Problem Description The inversion number of a given number sequence a1, a2, ..., a

#1141 : 二分&#183;归并排序之逆序对(归并排序)

#1141 : 二分·归并排序之逆序对 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回.上上回以及上上上回里我们知道Nettle在玩<艦これ>.经过了一番苦战之后,Nettle又获得了的很多很多的船. 这一天Nettle在检查自己的舰队列表: [list.png] 我们可以看到,船默认排序是以等级为参数.但实际上一个船的火力值和等级的关系并不大,所以会存在A船比B船等级高,但是A船火力却低于B船这样的情况.比如上图中77级的飞龙改二火力就小于55级的夕立

数组中的逆序对(归并排序的灵活运用)

这个题目如果没有限制你的时间复杂度,那么它的在O(n2) 里面完成的话, 那么就很简单 了. 但是如果发求你在O(n)的时间复杂度里面完成.那么这还是有点挑战性的. 题目的分析:对于逆序对的理解 先看方法: 如上面的所示,对于该算法以,我们首先将数组划分成一个一个的数字(为了排序),然后拆分成了 两个己排好序的数组. 那么如何计数逆序对呢? 如上图在(a)图中: 是两个排好序的数组,一个是5,7,另一个是4,6. 我们用两个指针P1和P2,一个指向左边那么数组的未尾,一个指向右边那么数组的未尾.

剑指offer——面试题36:数组中的逆序对(归并排序)

题目: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.输入一个数组,求出这个数组中的逆序对的总数. 思路: 采用归并排序的思想,将数组中的元素分割成子数组,先统计出子数组里的逆序对的个数.同时将这些子数组的数字排成有序的 慢慢往多的合并,在合并的过程中一面统计逆序对的个数,一面合并成一个数组时将里面排好序. 和合并排序类似,时间复杂度为O(nlogn) 下面是详细代码: #include<iostream> #include<vector> usi

面试题36:数组中的逆序对(归并排序思想)

在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对.输入一个数组,求出这个数组中的逆序对的总数.例如,有一个数组为Array[0..n] 其中有元素a[i],a[j].如果 当i<j时,a[i]>a[j],那么我们就称(a[i],a[j])为一个逆序对.在数组{7,5,6,4}中一共存在5对逆序对,分别是(7,6),(7,5),(7,4),(6,4),(5,4). 最简单的想法就是遍历每一个元素,让其与后面的元素对比,如果大于则count++,但是这样的时间复杂度是o

51nod1107(逆序对数&amp;归并排序)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107 题意:中文题诶- 思路:通过题意可以发现对于两点p1(x1, y1),p2(x2, y2), 若x1<x2&&y1>y2则线段p1p2满足要求,那么显然可以先按x值排下序,对应y序列的逆序对数目即为答案: 注意:对于x1==x2&&y1>y2的情况是不满足题意的,可以通过重载排序去除x值相等的情况下的y逆序对: 代

POJ 2299 逆序对

Crossings Time Limit: 2 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/100463 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent

POJ 2299 求逆序对(归并排序或树状数组)

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