摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 合併排序

應該有辦法DP  先暫時這樣吧

/********************************************************/

#include<stdlib.h>
#include<stdio.h>
int NUM[100001];
long long int ANS=0;
int MergeSort(int,int);
int Merge(int,int,int);
main()
{
  int N;
  while(scanf("%d",&N)==1&&N)
      {
         int a,b,c;
         for(a=0;a<N;a++)
            scanf("%d",&NUM[a]);
         ANS=0;
         MergeSort(0,N-1);
         if(ANS%2)
           puts("Marcelo");
         else
           puts("Carlos");
      }
  return 0;
}
int MergeSort(int l,int h)
{
   if(l<h)
      {
         int m=(l+h)/2;
         MergeSort(l,m);
         MergeSort(m+1,h);
         Merge(l,m,h);
      }
}
int Merge(int l,int m,int h)
{
   int in1=l,in2=m+1,out=l;
   int x[100001],top=0,a,b,D=0;
   while(in1<=m&&in2<=h)
      if(NUM[in1]>NUM[in2])
           x[top++]=NUM[in2++],D++;
      else
           x[top++]=NUM[in1++],ANS+=D;
   while(in1<=m)
       x[top++]=NUM[in1++],ANS+=D;
   while(in2<=h)
       x[top++]=NUM[in2++];
   for(a=l,b=0;a<=h;a++,b++)
      NUM[a]=x[b];
}