[ACM ] 10327
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
( 未必需要依照此格式，文章條理清楚即可 )
題號：10327
遇到的問題:
(此題以AC)
本來小弟我是用bubble sort但是方法沒效率,
所以被老師要求要想出Ｏ(nlogn)的方法,
所以上網找到有人用merge sort,搞了半天終於ac...
但是我不太會解釋耶...
所以想請教各位版上大大要如何解釋在merge裡紀錄次數的方式
有問題的code： (請善用置底文的標色功能)
#include <stdio.h>
#include <stdlib.h>
int ans;
void merge(int *data, int *left, int *right, int x, int y)
{
int i,j,k,d;
i=j=k=d=0;
while (i<x && j<y)
{
if(left[i]>right[j])
{
data[k++]=right[j++]; d++;
}
else
{
data[k++]=left[i++]; ans+=d;
}
}
while (i<x)
{
data[k++]=left[i++]; ans+=d;
}
while (j<y)
{
data[k++]=right[j++];
}
}
int mergesort( int *data , int n)
{
int x,y,i,j,left[n>>1],right[n-(n>>1)];
if (n<=1) return 0;
x=n/2; y=n-x;
for (i=0;i<x;i++)
left[i]=data[i];
for (i=0;i<y;i++)
right[i]=data[x+i];
mergesort(left,x);
mergesort(right,y);
merge(data,left,right,x,y);
}
int main(void)
{
int i, n, data[1000];
while(scanf("%d",&n)==1)
{
for (i=0;i<n;i++)
scanf("%d",&data[i]);
ans=0;
mergesort(data, n);
printf("Minimum exchange operations : %d\n",ans);
}
}
補充說明：
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.117.180.29
推
03/05 16:57, , 1F
03/05 16:57, 1F
→
03/05 16:57, , 2F
03/05 16:57, 2F
→
03/05 17:04, , 3F
03/05 17:04, 3F
推
03/05 17:07, , 4F
03/05 17:07, 4F
→
03/05 17:15, , 5F
03/05 17:15, 5F
推
03/05 17:33, , 6F
03/05 17:33, 6F
→
03/05 17:34, , 7F
03/05 17:34, 7F
推
03/06 16:18, , 8F
03/06 16:18, 8F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
