一本通【1182：合影效果】，插入排序解决

曾经终败给现在 2022-12-28 08:22 107阅读 0赞

## 1182：合影效果 ##

> 时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】  
小云和朋友们去爬香山，为美丽的景色所陶醉，想合影留念。如果他们站成一排，男生全部在左（从拍照者的角度），并按照从矮到高的顺序从左到右排，女生全部在右，并按照从高到矮的顺序从左到右排，请问他们合影的效果是什么样的（所有人的身高都不同）？

【输入】  
第一行是人数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 <iostream>
    #include <cstring>
    #include <stdio.h>
    using namespace std;
    void insertion_sort_ls(double arr[], int len) // 插入排序从大到小
    { 
        for (int i = 1; i < len; i++)
        { 
            double key = arr[i];
            int j = i - 1;
            while ((j >= 0) && (key > arr[j]))
            { 
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    void insertion_sort_sl(double arr[], int len) // 插入排序从小到大
    { 
        for (int i = 1; i < len; i++)
        { 
            double key = arr[i];
            int j = i - 1;
            while ((j >= 0) && (key < arr[j]))
            { 
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    int main()
    { 
        double mmale[80], ffemale[80];
        int midx = 0, fidx = 0;
        int n;
        double tmp;
        cin >> n;
        char str[20];
        for (int i = 0; i < n; i++)
        { 
            cin >> str;
            cin >> tmp;
            if (strcmp(str, "male") == 0)
            { 
                mmale[midx] = tmp;
                midx++;
            }
            else if (strcmp(str, "female") == 0)
            { 
                ffemale[fidx] = tmp;
                fidx++;
            }
        }
        insertion_sort_sl(mmale, midx);
        insertion_sort_ls(ffemale, fidx);
        for (int i = 0; i < midx; i++)
            printf("%.2lf ", mmale[i]);
        for (int i = 0; i < fidx; i++)
            printf("%.2lf ", ffemale[i]);
        cout << endl;
        // for (int i = 0; i < n; i++)
        // { 
        // gets(str);
        // scanf("%d", &tmp);
        // // if (str == "male")
        // if (strcmp(str, "male") == 0)
        // { 
        // male.push_back(tmp);
        // }
        // // else if (str == "female")
        // else if (strcmp(str, "female") == 0)
        // { 
        // female.push_back(tmp);
        // }
        // }
        // sort(male.begin(), male.end());
        // sort(female.begin(), female.end());
        // for (int i = 0; i < male.size(); i++)
        // cout << male[i] << " ";
        // for (int i = 0; i < female.size(); i++)
        // cout << female[i] << " ";
        // cout << endl;
        return 0;
    }
    
    /* 6 male 1.72 male 1.78 female 1.61 male 1.65 female 1.70 female 1.56 */

其中最重要的两个函数就是插入排序函数

void insertion_sort_ls(double arr[], int len)
    { 
        for (int i = 1; i < len; i++)
        { 
            double key = arr[i];
            int j = i - 1;
            while ((j >= 0) && (key > arr[j]))
            { 
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    void insertion_sort_sl(double arr[], int len)
    { 
        for (int i = 1; i < len; i++)
        { 
            double key = arr[i];
            int j = i - 1;
            while ((j >= 0) && (key < arr[j]))
            { 
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

比选择排序快，但是这道题选择排序也可以用，但是数据量一大，O(n2)速度的选择排序的劣势就会出现。