HDOJ 1009 FatMouse' Trade （贪心）

//原题目地址
//http://acm.hdu.edu.cn/showproblem.php?pid=1009
//经典贪心题目
/*
其实贪心都是还是其次的，
这里用结构体来装Room的信息，
然后用sort来排序.

*/


#include<iostream>
#include<algorithm>
using namespace std;
typedef struct _NODE_
{
    double J;        //JavaBean 
    double F;        //cat food 
    double V;        //性价比 
    
}Node;

Node Room[1001];    //定义出来1001个结构体，题目说明了最多1000个房间 

bool cmp(Node x, Node y)            //排序规则 降序 
{
    return x.V > y.V;
}

int main()
{
    int N,i;
    double M,ans;
    while(scanf("%lf%d",&M,&N)!=EOF)
    {
        if(M==-1&&N==-1)
            break;
        for(i=0;i<N;i++)        //读文件 
        {
            scanf("%lf%lf",&Room[i].J,&Room[i].F);
            Room[i].V = Room[i].J/Room[i].F;
        }    
        sort(Room,Room+N,cmp);    //按照性价比排序 

        ans = 0;
        for(i=0;i<N;i++)    //贪心算法 
        {
            if(M>=Room[i].F)
            {
                ans+=Room[i].J;
                M-=Room[i].F;
            }
            else
            {
                ans+=(Room[i].J/Room[i].F)*M;
                break;
            }
        }
        printf("%.3lf
",ans);    //输出结果，注意格式 
    }
    return 0;
}

 1 //qsort版本 转
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 
 5 const int MAXN = 1010;
 6 struct node
 7 {
 8     double j,f;
 9     double r;
10 }a[MAXN];
11 int cmp(const void *a,const void *b)//从大到小排序 
12 {
13     struct node *c=(node *)a;
14     struct node *d=(node *)b;
15     if(c->r > d->r) return -1;
16     else return 1;
17 }    
18 int main()
19 {
20     int N;
21     double M;
22     double ans;
23     while(scanf("%lf%d",&M,&N))
24     {
25         if(M==-1&&N==-1) break;
26         for(int i=0;i<N;i++)
27         {
28            scanf("%lf%lf",&a[i].j,&a[i].f);
29            a[i].r=(double)a[i].j/a[i].f;
30         }    
31         qsort(a,N,sizeof(a[0]),cmp);
32         ans=0;
33         for(int i=0;i<N;i++)
34         {
35             if(M>=a[i].f)
36             {
37                 ans+=a[i].j;
38                 M-=a[i].f;
39             }    
40             else 
41             {
42                 ans+=(a[i].j/a[i].f)*M;
43                 break;
44             }    
45         }   
46         printf("%.3lf
",ans); 
47     }    
48     return 0;
49 }