1149: 零起点学算法56——青年歌手大奖赛

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

Description

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

Input

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

Output

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

" class="reference-link">Sample Input

3 99 98 97
4 100 99 98 97

Sample Output

98.00
98.50

Source

零起点学算法

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

但是文章中有一处错误，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);
    }
}