1182：合影效果

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 12645 ??? 通過數: 7214

【題目描述】

小云和朋友們去爬香山，為美麗的景色所陶醉，想合影留念。如果他們站成一排，男生全部在左（從拍照者的角度），并按照從矮到高的順序從左到右排，女生全部在右，并按照從高到矮的順序從左到右排，請問他們合影的效果是什么樣的（所有人的身高都不同）？

【輸入】

第一行是人數n（2 <= n <= 40，且至少有1個男生和1個女生）。

后面緊跟n行，每行輸入一個人的性別（男male或女female）和身高（浮點數，單位米），兩個數據之間以空格分隔。

【輸出】

n個浮點數，模擬站好隊后，拍照者眼中從左到右每個人的身高。每個浮點數需保留到小數點后2位，相鄰兩個數之間用單個空格隔開。

【輸入樣例】

6 male 1.72 male 1.78 female 1.61 male 1.65 female 1.70 female 1.56

【輸出樣例】

1.65 1.72 1.78 1.70 1.61 1.56

【分析】

? ? ? ? 歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

【參考代碼】

#include <stdio.h>
#include <string.h>
#define N 50
double a[N],b[N],r[N];
void msort(int s,int t) ?//歸并排序?
{
?? ?int i,j,mid,k;
?? ?if(s==t) ? ? ?//如果只有一個數字則返回，無需排序?
?? ??? ?return;
?? ?mid=(s+t)/2;
?? ?
?? ?msort(s,mid); ? ?//分解左序列?
?? ?msort(mid+1,t); ?//分解有序列?
?? ?
?? ?i=s;
?? ?j=mid+1;
?? ?k=s;
?? ?
?? ?while(i<=mid && j<=t) ?//接下來合并?
?? ?{
?? ??? ?if(a[i]<=a[j])
?? ??? ?{
?? ??? ??? ?r[k]=a[i];
?? ??? ??? ?k++;
?? ??? ??? ?i++;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?r[k]=a[j];
?? ??? ??? ?k++;
?? ??? ??? ?j++;
?? ??? ?}
?? ?}
?? ?while(i<=mid) ?//復制左邊子序列剩余?
?? ?{
?? ??? ?r[k]=a[i];
?? ??? ?k++;
?? ??? ?i++;
?? ?}
?? ?while(j<=t) ? ?//復制右邊子序列剩余?
?? ?{
?? ??? ?r[k]=a[j];
?? ??? ?k++;
?? ??? ?j++;
?? ?}
?? ?for(i=s;i<=t;i++)
?? ??? ?a[i]=r[i];
}
void cmpsort(int n) //比較排序?
{
?? ?int i,j;
?? ?double t;
?? ?for(i=0;i<n-1;i++)
?? ?{
?? ??? ?for(j=i+1;j<n;j++)
?? ??? ?{
?? ??? ??? ?if(b[i]<b[j])
?? ??? ??? ?{
?? ??? ??? ??? ?t=b[i];
?? ??? ??? ??? ?b[i]=b[j];
?? ??? ??? ??? ?b[j]=t;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
int main()
{
?? ?int i,j=0,k=0,n;
?? ?double x;
?? ?char s[N];
?? ?scanf("%d",&n);
?? ?for(i=0;i<n;i++)
?? ?{
?? ??? ?scanf(" %s %lf",s,&x);
?? ??? ?if(strcmp(s,"male")==0)
?? ??? ??? ?a[j++]=x;
?? ??? ?else
?? ??? ??? ?b[k++]=x;
?? ?}
?? ?msort(0,j-1);
?? ?cmpsort(k);
?? ?for(i=0;i<j;i++)
?? ??? ?printf("%.2lf ",a[i]);
?? ?for(i=0;i<k;i++)
?? ??? ?printf("%.2lf ",b[i]);
?? ?
}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1182

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1182：合影效果）——归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。