归并排序 例题即模版 XMU1328 hdu3743
[cpp]
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000100
int input[MAXN] = {0};
int tmp[MAXN];
void merge(int left, int middle, int right)
{
int i, j, k;
i = left, j= middle+1, k = 1;
while(i<= middle && j <= right)
{
if(input[j] < input[i])
{
tmp[k++] = input[j++];
}
else
{
tmp[k++] = input[i++];
}
}
while(i <= middle)
tmp[k++] = input[i++];
while(j <= right)
tmp[k++] = input[j++];
for(i = left, k = 1; i<= right; i++, k++)
input[i] = tmp[k];
}
void merge_sort(int left, int right)
{
if(left < right)
{
int middle = (left + right)/2;
merge_sort(left, middle);
merge_sort(middle+1, right);
merge(left, middle, right);
}
}
int main(){
int n,i;
while( scanf("%d",&n)&&n)
{
for(i=0;i<n;++i)
scanf("%d",&input[i]);
merge_sort(0,n-1);
for(i=0;i<n-1;++i)
printf("%d ",input[i]);
printf("%d\n",input[i]);
}
return 0;
}
上面是模版
只要看下代码 就能理解是如何实现的了
下面是一个应用 XMU1328
1328.不高兴的bobo
Time Limit: 2000 MS Memory Limit: 65536 K
Total Submissions: 589 (85 users) Accepted: 55 (42 users)
Description
Bobo手下有n个小弟，身高分别是a1，a2……an，bobo看他们高矮不一，于是很不高兴，定义有两个小弟不按高矮站时，bobo的不高兴值加1（即(i,j)，i<j,ai>aj），问bobo的总不高兴值为多少。
Input
一个整数n，表示bobo有n个小弟。
以下有n个整数ai，代表小弟的身高。
N<=10^6,ai<2^32
Output
一个整数为bobo的不高兴值。
Sample Input
5
5 4 3 2 1
Sample Output
10
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000100
int input[MAXN] = {0};
int tmp[MAXN];
long long result;
void merge(int left, int middle, int right)
{
int i, j, k;
i = left, j= middle+1, k = 1;
while(i<= middle && j <= right)
{
if(input[j] < input[i])
{
tmp[k++] = input[j++];
result += middle - i + 1;
}
else
{
tmp[k++] = input[i++];
}
}
while(i <= middle)
tmp[k++] = input[i++];
while(j <= right)
tmp[k++] = input[j++];
for(i = left, k = 1; i<= right; i++, k++)
input[i] = tmp[k];
}
void merge_sort(int left, int right)
{
if(left < right)
{
int middle = (left + right)/2;
merge_sort(left, middle);
merge_sort(middle+1, right);
merge(left, middle, right);
}
}
int main(){
int n,i;
scanf("%d",&n);
for(i=0;i<n;++i)
scanf("%d",&input[i]);
result=0;
merge_sort(0,n-1);
printf("%lld\n",result);
return 0;
}
下面这个题和上面是一抹一样的
Frosh Week
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1027 Accepted Submission(s): 319
补充：软件开发 , C++ ,
