首页 > ACM题库 > HDU-杭电 > hdu 2014 青年歌手大奖赛_评委会打分-高精度-[解题报告]C++
2013
12-26

hdu 2014 青年歌手大奖赛_评委会打分-高精度-[解题报告]C++

青年歌手大奖赛_评委会打分

问题描述 :

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

输入:

输入数据有多组,每组占一行,每行的第一个数是n(2<n<=100),表示评委的人数,然后是n个评委的打分。

输出:

输入数据有多组,每组占一行,每行的第一个数是n(2<n<=100),表示评委的人数,然后是n个评委的打分。

样例输入:

3 99 98 97
4 100 99 98 97

样例输出:

98.00
98.50

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2014

要实现的算法是:求整个数组的和、在数组中找最值。
找最值,可以先把第一个元素赋给max、min变量,做一次遍历,一一比较,把最大值存入max,最小值存入min。
也可以直接对数组进行排序,然后从第二个加到倒数第二个,这样就可以了,省去减两个最值。
 

编码建议

Programing
  我的代码采用的是第一种方法。因为对于本题来说,它的效率是O(N)。
算法不难,可以直接看代码

这里稍微讨论一下第二种方法。
对于排序,我们可以直接调用库函数qsort();

语法:

#include <stdlib.h>
void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );

功能: 对buf 指向的数据(包含num 项,每项的大小为size)进行快速排序。如果函数compare 的第一个参数小于第二个参数,返回负值;如果等于返回零值;如果大于返回正值。函数对buf 指向的数据按升序排序。

#include <stdio h="">#include <stdlib h="">int cmp(const double *a, const double *b){return *a &gt; *b ? 1 : *a &lt; *b ? -1 : 0;}int main(void){int n, i;double x, y[100];while (scanf(&quot;%d&quot;, &n) != EOF){for (i = 0 ; i &lt; n ; i++)scanf(&quot;%lf&quot;, y + i);qsort(y, n, sizeof(double), cmp);for (x = 0, i = 1 ; i &lt; n - 1 ; i++)x += y[i];printf(&quot;%.2f\n&quot;, x / (n - 2));}return 0;}</stdlib></stdio>

你可能有疑问,为什么cmp函数不直接用return *a – *b;
这也就是我不打算用这种方法的原因了(虽然上面的代码可以Accpted),这就是这段代码的不稳定因素。
我们来做个实验:

#include <math h="">#include <stdio h="">int main(void){int i;double x;x = 0.123456;printf(&quot;%lf\n&quot;, x);for (i = 0 ; x - floor(x); i++)x *= 10;printf(&quot;%d\n&quot;, i);return 0;}</stdio></math>

上面的代码的作用就是确定X小数点后有几位。
我相信所有人都知道它有6位小数。但它的运行结果却是17(因编译器而异)。
你可以自己复制代码去验证一下。
我们在循环体里插入printf("%lf\n", floor(x));看看它的变化是怎样的。

运行结果:
1.000000
12.000000
123.000000
1234.000000
12345.000000
123455.000000
1234559.000000
12345599.000000
123455999.000000
1234559999.000000
12345599999.000000
123455999999.000000
1234559999999.000000
12345599999999.000000
123455999999999.000000
1234559999999999.000000
12345599999999998.000000

这就是double型数据的精度问题。这是我们无法人为地控制的。所以建议尽量避免double的高精度运算。  

#include <stdio.h>

int main(void)
{
    int n, i;
    double min, max;
    double x, y;
    
    while (scanf("%d", &n) != EOF)
    {
        scanf("%lf", &x);
        min = max = x;
        for (i = 1 ; i < n ; i++)
        {
            scanf("%lf", &y);
            x += y;
            if (y > max) max = y;
            if (y < min) min = y;
        }
        printf("%.2lf\n", (x - min - max) / (n - 2));
    }

    return 0;
}

解题转自:http://blog.csdn.net/basementman/article/details/16920477


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢