首页 > 代码库 > HDU 1009贪心

HDU 1009贪心

2024-07-24 03:36:22   225人阅读

代码如下。需要说明的是，之前一直WA，发现对这题来说，难点不是贪心，是对浮点数的处理，做题经验不足会导致一直不能AC。在代码第43行，用1.0*m*x[i].a/x[i].b就能AC，但是如果直接用x[i].re*m则会WA。其实计算re只是为了排序，在最后计算结果的时候如果还用这个浮点数就会导致多个浮点误差累积，使误差会更大。而直接用m*x[i].a/x[i].b这样做，由于先算的是整数之间的乘法，然后再算一次除法，那么得到浮点数的误差就只有一次，而不是上一种情况的多次误差累积。

 1 #include <stdio.h> 2 #include <stdlib.h> 3  4 typedef struct{ 5     int a,b; 6     float re; 7 }node; 8  9 int cmp(const void* a,const void * b)10 {11     return (*(node *)a).re < (*(node *)b).re?1:-1;12 }13 14 node x[1005];15 16 int main()17 {18     int m,n,i;19     float max;20     while(scanf("%d%d",&m,&n))21     {22         if(m==-1 || n==-1)break;23         max = 0;24         for(i=0; i<n; i++)25         {26             scanf("%d%d",&x[i].a,&x[i].b);27             if(x[i].b==0)28                 x[i].re = 10000;29             else x[i].re = (x[i].a*1.0)/x[i].b;30 31         }32         qsort(x,n,sizeof(node),cmp);33         for(i=0; i<n; i++)34         {35             /*printf("%d:%f\n",i,x[i].re);*/36             if(x[i].b < m)37             {38                 max += x[i].a;39                 m -= x[i].b;40             }41             else if(x[i].b > m)42             {43                 max += 1.0*m*x[i].a/x[i].b; /*change to m*x[i].re can‘t AC*/44                 break;45             }46             else47             {48                 max += x[i].a;49                 break;50             }51         }52         printf("%.3f\n",max);53     }54     return 0;55 }

HDU 1009贪心


联系
我们