Question

杭电ACM4310题,简单贪心,一直WA,求大牛指教!!!!题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=431

#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

1.排序时可以用交叉相乘的方式可以避免精度问题
2.cmp函数改为减法就行了
int cmp( const void *a , const void *b )
{
struct In *c = (In*)a;
struct In *d = (In*)b;
return c->hp*d->dps-d->hp*c->dps;
}

#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;
return c->hp*d->dps-d->hp*c->dps;
}
int main()
{
freopen("test.txt","r",stdin);
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;
}
}
}
cout<<sum<<endl;
}
return 0;
}