Question

杭电ACM4310题,简单贪心,一直WA,求大牛指教!!!

题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4310
代码:
#include<stdio.h>
#include<stdlib.h>
struct In
{
double bi;
int dps;
int hp;
}hero[100];
int cmp( const void *a , const void *b )
{
struct In *c = (In*)a;
struct In *d = (In*)b;
if(c -> bi != d -> bi)
return d -> bi > c -> bi;
else
return d -> hp - c -> hp;
}
int main()
{
int n, i, j, k;
__int64 sum;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i ++)
{
scanf("%d %d", &hero[i].dps, &hero[i].hp);
hero[i].bi = hero[i].dps * 1.000 / hero[i].hp * 1.000;
}
qsort(hero, n, sizeof(hero[0]), cmp);
sum = 0;
for(i = 0; i < n; i ++)
{
for(j = hero[i].hp; j > 0; j --)
{
for(k = i; k < n; k ++)
{
sum = sum + hero[k].dps;
}
}
}
printf("%I64d\n", sum);
}
return 0;
}

Answer 1

我也玩dota，如果我是高等级肉盾英雄，对面三noob砍我的话，玩的时候不能用数学头脑去计算最后秒法，通常是大概看一下战略是：

残血的第一

没有残血的，高输出(DPS)的先撸死

最后和高防御低输出的对砍 (这里只有力量对应的HP，没有防御装备)

你的算法是，首先用dps/hp来判断先砍谁，其次从hp，这个是我们玩游戏目测英雄数据时的做法。

从严谨的数学角度是对的，但是从计算机的角度是不对的，因为你的double浮点是不准确的，0.1计算机double就不是0.1 。所以你应该用乘法去比较

#include<stdio.h>
#include<stdlib.h>
struct In
{
  double bi;
  int dps;
  int hp;
}hero[100];
int cmp( const void *a , const void *b )
{
    struct In *c = (In*)a;
    struct In *d = (In*)b;
    /*if(c -> bi != d -> bi)
        return d -> bi > c -> bi;
    else
        return d -> hp - c -> hp;*/
    return ( d->dps * c->hp ) - (d->hp * c->dps );
}
int main()
{
    int n, i, j, k;
    __int64 sum;
    while(scanf("%d", &n) != EOF)
    {
        for(i = 0; i < n; i ++)
        {
            scanf("%d %d", &hero[i].dps, &hero[i].hp);
            hero[i].bi = hero[i].dps * 1.000 / hero[i].hp * 1.000;
        }
        qsort(hero, n, sizeof(hero[0]), cmp);
        sum = 0;
        for(i = 0; i < n; i ++)
        {
            for(j = hero[i].hp; j > 0; j --)
            {
                for(k = i; k < n; k ++)
                {
                    sum = sum + hero[k].dps;
                }
            }
        }
        printf("%I64d\n", sum);
    }
    return 0;
}

Answer 2

http://zhidao.baidu.com/question/368277364?&oldq=1
看看这个，如果你还有心继续acm，自己检错是少不了的