首页 > ACM题库 > HDU-杭电 > HDU 1009 FatMouse’ Trade-贪心-[解题报告] C++
2013
11-26

HDU 1009 FatMouse’ Trade-贪心-[解题报告] C++

FatMouse’ Trade

问题描述 :

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

输入:

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1′s. All integers are not greater than 1000.

输出:

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

样例输入:

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

样例输出:

13.333
31.500

解题报告:

大意:一只老鼠有M磅的猫粮,另外有一只猫控制了老鼠的N个房间,这些房间里面放了老鼠爱吃的绿豆,给出每个房间的绿豆数量,和这个房间的绿豆所需要的猫粮数,现在要求老鼠用这M磅的猫粮最多能换到多少它爱吃的绿豆?

贪心题,由于所有的绿豆都是一样的,所以如果老鼠想要换到最多的绿豆,便可以换猫控制的房间里面最便宜的绿豆,也就是说先换取单位数量的绿豆所需要最少的猫粮的房间里的绿豆,这样就可以保证换到的绿豆是最多的。具体实现可以用一个结构体,里面保存每个房间里面有的绿豆的数量和换取这个房间的绿豆时所需要的猫粮的数量和换取这个房间的 单位重量的绿豆所需要的猫粮数(以下简称单价),然后再按照单价升序给这些结构体排一次序,这时就可以从最便宜的绿豆开始换了。

 #include<stdio.h>
  #include<algorithm>
  struct node {
      double j,f,velu;
  }java[1000+5];
  double M;
  int N;
  bool cmp(node a,node b) {
      return a.velu>b.velu;
 }
 int main() {
     while(scanf("%lf%d",&M,&N)&&!(M==-1||N==-1)) {
         double sum=0;
         for(int i=1;i<=N;++i) {
             scanf("%lf%lf",&java[i].j,&java[i].f);
             java[i].velu=1.0*java[i].j/java[i].f;
         }
         if(N>1)
         std::sort(java+1,java+N+1,cmp);
         for(int i=1;;++i) {
             if(N==0)
             break;
             if(M>=java[i].f) {
                 M-=java[i].f;
                 sum+=java[i].j;
             }
             else{
                 sum+=1.0*M*java[i].j/java[i].f;
                 break;
             }
         }
         printf("%.3lf\n",sum);
     }
     return 0;
 }

 


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  3. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!