首页 > 代码库 > 贪心算法 hdu 1009

贪心算法 hdu 1009

1、因为要排序只派j[i]/f[i],不能知道f[i]和j[i]各自排序后的顺序,因此要用到结构体

2、用sort(ware,ware+n,cmp) cmp 为俩个数组的元素比较大小的布尔值

技术分享

#include<iostream>#include<algorithm>using namespace std;struct warehouse{    double j,f,p;};warehouse ware[1005];bool cmp(warehouse a,warehouse b){    if(a.p>=b.p)return true;    else return false;}int main(){     int m,n;     double sum;     while(cin>>m>>n)     {         sum=0;         if(m==-1&&n==-1)            break;         for(int i=0;i<n;i++)         {             cin>>ware[i].j>>ware[i].f;             ware[i].p=ware[i].j/ware[i].f;         }         sort(ware,ware+n,cmp);         for(int i=0;i<n&&m;i++)         {             if(m>ware[i].f)                {                    m=m-ware[i].f;                    sum=sum+ware[i].j;                }             else                {                    sum+=(m*1.0/ware[i].f)*ware[i].j;                    m=0;                }         }         printf("%.3f\n",sum);     }    return 0;}

 

贪心算法 hdu 1009