巢穴

about:blank

P2299

逆序对,归并排序统计一下.
这题我是真的wa哭了..以前没写过归并排序.虽然知道思路..
这次就真的写尴尬了..
搞到最后专门去找别人代码看来开去都没发现自己哪写错了..
终于..最后发现了.....
于是我加上了&&pl<=mid 这个东西..为啥加上..就不解释了..很尴尬的问题

#include <iostream>
//#include <fstream>
//#include <stdio.h>
using namespace std;
const int MAXN=500001;
int n;
long num[MAXN];
long c[MAXN];
long long result=0ll;
//ifstream fin("1.txt");

void sort(int l,int r)
{
 if (l==r)
 {
  return;
 }
 int mid=(l+r)/2;
 sort(l,mid);
 sort(mid+1,r);
 int t=l;
 int pl=l,pr=mid+1;
 while(t<=r)
 {
  if (pr>r||(num[pl]<=num[pr]&&pl<=mid)) {c[t++]=num[pl++];continue;}
  if (pl>mid||(num[pr]<num[pl]&&pr<=r)) { if (pl<=mid) result+=mid-pl+1;c[t++]=num[pr++];continue;}
 }
 for (int i=l;i<=r;i++)
     num[i]=c[i];
     
}
int main()
{
    while(1)
    {
     cin>>n;
     if (0==n) break;
     for (int i=1;i<=n;i++)
         cin>>num[i];
     //result=0;
     result=0ll;
     sort(1,n);
     cout<<result<<endl;
    }
//    system("pause");
    return 0;
}



 

posted on 2009-10-20 17:02 Vincent 阅读(506) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理