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下載地址