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<=r)
     {
          if(aa[i]>aa[j])
          {
               bb[t++]=aa[j++];
               s+=m-i+1;
          }
          else
          {
               bb[t++]=aa[i++];
          }
     }
     while(i<=m)
          bb[t++]=aa[i++];
     while(j<=r)
          bb[t++]=aa[j++];
     for(int i=0;i<t;i++)     //并!不能省,否则归并排序不完整
     {
          aa[l+i]=bb[i];
     }
}
void Msort (int L,int R)
{
    int cen;
    if(L<R)
    { cen=(L+R)/2;
    Msort(L,cen);
    Msort(cen+1,R);
    merge(L,cen,R);

    }

}
void merge_sort(int *a,int n)
{ Msort(0,n-1);     //做接口;

}
int main()
{
    int n,d=1;
    cin>>n;

    for(int i=0;i<n;i++)
    {   memset(aa,0,sizeof(aa));
        memset(bb,0,sizeof(bb));

       int q;
        cin>>q;

        if(q==0)break;

    for(int j=0;j<q;j++)
    {
        cin>>aa[j];
    }
    merge_sort(aa,q);
cout<<"Scenario #"<<d<<‘:‘<<endl;
    cout<<s<<endl<<endl;
     s=0;d++;

     }
    return 0;

}
时间: 05-18

POJ 1804的相关文章

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

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

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

逆序数的求法

求一个数列的逆序数 逆序对:数列s[1],a[2],a[3]-中的任意两个数s[i],s[j] (i<j),如果s[i]>s[j],那么我们就说这两个数构成了一个逆序对 逆序数:一个数列中逆序对的总数 如数列 3 5 4 8 2 6 9 (5,4)是一个逆序对,同样还有(3,2),(5,2),(4,2)等等 那么如何求得一个数列的逆序数呢? 方法1:一个一个的数 最简单也是最容易想到的方法就是,对于数列中的每一个数s[i],遍历数列中的数s[j](其中j<i),若s[i]<s[j]

POJ 3449 Geometric Shapes --计算几何,线段相交

题意: 给一些多边形或线段,输出与每一个多边形或线段的有哪一些多边形或线段. 解法: 想法不难,直接暴力将所有的图形处理成线段,然后暴力枚举,相交就加入其vector就行了.主要是代码有点麻烦,一步一步来吧. 还有收集了一个线段旋转的函数. Vector Rotate(Point P,Vector A,double rad){ //以P为基准点把向量A旋转rad return Vector(P.x+A.x*cos(rad)-A.y*sin(rad),P.y+A.x*sin(rad)+A.y*co