270      阿里云  技术社区[云栖]

cf 204 div2 D. Jeff and Furik 逆序对

     又一次看错题意……题目是两个人，一个人自己主观选择，一个人抛硬币，因为算期望，所以抛硬币那人可以无视掉，求出逆序对个数m，m为奇答案是2m-1，否则2m

    太囧

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
int org[100000];
int c[100000];
int ans=0;
void out(int *a,int n)
{
   for(int i=0;i<n;i++)
      printf("%d ",a[i]);
   puts("");
}
int meg(int l,int mid,int r)
{
    int i=l,j=mid+1,k=0;
    while(i<=mid)
    {
       while(j<=r&&org[i]>org[j])
          c[k++]=org[j++];
       ans+=j-mid-1;
       c[k++]=org[i++];
    }
    while(j<=r)c[k++]=org[j++];
    k=0;
    while(l<=r)org[l++]=c[k++];
}
void count(int l,int r)
{
    if(l<r)
    {
       int mid=(l+r)>>1;
       count(l,mid);
       count(mid+1,r);
       meg(l,mid,r);
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
       ans=0;
        int i;
        for(i=0;i<n;i++)
           scanf("%d",&org[i]);
        count(0,n-1);
        double t;
        if(ans%2==0)ans*=2;
        else ans=ans*2-1;
        printf("%.6f\n",(double)(ans));
    }
}

最后更新：2017-04-03 14:53:43

  上一篇： android.intent.action.DATE_CHANGED不广播的原因

  下一篇： ubuntu12.04 64位系统配置jdk1.6和jdk-6u20-linux-i586.bin下载地址