1149: 零起点学算法56——青年歌手大奖赛_评委会打分

谁践踏了优雅 2023-01-11 08:50 134阅读 0赞

## Description ##

青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。

## Input ##

青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。

## Output ##

对于每组输入数据，输出选手的得分，结果保留2位小数，每组输出占一行。

## Sample Input ![5f8f312f51791b8bb0ed0ae07c2ffa43.gif][] ##

3 99 98 97
    4 100 99 98 97

## Sample Output ##

98.00
    98.50

## Source ##

[零起点学算法][Link 1]

## Code ##

一开始想排序，然后去掉一头一尾，但是答案始终不正确

#include<stdio.h>
    #include<iostream>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[20]={999};
            int t=-10;
            int sum=0;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
                sum+=a[i];
            }
            for(int i=0;i<n;i++)
            {
                if(a[i]>a[i+1])
                {
                    t=a[i+1];
                    a[i+1]=a[i];
                    a[i]=t;
                }
            }
            sum=sum-a[0]-a[n-1];
            float ave=(float)sum/(n-2);
            printf("%.2f\n",ave);
        }
    }

因为这题想用冒泡排序，但是冒泡排序是需要用双层的，如果按照旧代码就只进行了一次冒泡排序。改进如下

#include<stdio.h>
    #include<iostream>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[20]={999};
            int t=-10;
            int sum=0;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
                sum+=a[i];
            }
            ///i的范围0~n-2，j的范围n-2~0,就可以实现a[0]与后面直到a[n-1]的大小比较
            for(int i=0;i<n-1;i++)
            {
                for(int j=0;j<n-1-i;j++)
                if(a[j]>a[j+1])
                {
                    t=a[j+1];
                    a[j+1]=a[j];
                    a[j]=t;
                }
            }
            sum=sum-a[0]-a[n-1];
            float ave=(float)sum/(n-2);
            printf("%.2f\n",ave);
        }
    }

这个方法每一轮都要遍历所有的元素，因此时间复杂度是O(n^2)，改进如下，设置标志量flag，若进行排序中则flag=1,表示还需要继续排序，否则直接跳出循环。这样的话时间复杂度有效降低。

#include<stdio.h>
    #include<iostream>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[20]={999};
            int t=-10;
            int sum=0;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
                sum+=a[i];
            }
            ///i的范围0~n-2，j的范围n-2~0,就可以实现a[0]与后面直到a[n-1]的大小比较
    
            for(int i=0;i<n-1;i++)
            {
                int flag=0;
                for(int j=0;j<n-1-i;j++)
                if(a[j]>a[j+1])///说明仍然需要排序
                {
                    t=a[j+1];
                    a[j+1]=a[j];
                    a[j]=t;
                    flag=1;
                }
                ///没被排，说明是顺序的
                if(flag==0)
                    break ;
            }
            sum=sum-a[0]-a[n-1];
            float ave=(float)sum/(n-2);
            printf("%.2f\n",ave);
        }
    }

冒泡排序法参考文章[https://blog.csdn.net/lu\_1079776757/article/details/80459370][https_blog.csdn.net_lu_1079776757_article_details_80459370]

但是文章中有一处错误，flag=0的位置放错了，正确版是我的代码

此题还有一种解法，没有进行排序，直接找出最大最小值即可

#include<stdio.h>
    #include<iostream>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[20]={0};
            int max=-10;
            int min=999;
            int t=-1;
            int sum=0;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
                sum+=a[i];
            }
            ///i的范围0~n-2，j的范围n-2~0,就可以实现a[0]与后面直到a[n-1]的大小比较
    
            for(int i=0;i<n;i++)
            {
                if(a[i]>max)///说明仍然需要排序
                    max=a[i];
                if(a[i]<min)
                    min=a[i];
            }
            sum=sum-max-min;
            float ave=(float)sum/(n-2);
            printf("%.2f\n",ave);
        }
    }

[5f8f312f51791b8bb0ed0ae07c2ffa43.gif]: /images/20221119/bd80dde517ae49ea9ab0b5d182951bdd.png
[Link 1]: https://oj.wustacm.top/problemset.php?search=%E9%9B%B6%E8%B5%B7%E7%82%B9%E5%AD%A6%E7%AE%97%E6%B3%95&searchmode=source&soj=0
[https_blog.csdn.net_lu_1079776757_article_details_80459370]: https://blog.csdn.net/lu_1079776757/article/details/80459370