编程与算法

[ACM]hdoj 1009 FatMouse’ Trade

Problem Description:
FatMouse prepared M pounds of cat food, ready to trade with thecats guarding the warehouse containing his favorite food,JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds ofJavaBeans and requires F[i] pounds of cat food. FatMouse does nothave to trade for all the JavaBeans in the room, instead, he mayget J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of catfood. Here a is a real number. Now he is assigning this homework toyou: tell him the maximum amount of JavaBeans he can obtain.
Input:
The input consists of multiple test cases. Each test case beginswith a line containing two non-negative integers M and N. Then Nlines follow, each contains two non-negative integers J[i] and F[i]respectively. The last test case is followed by two -1’s. Allintegers are not greater than 1000.
Output:
For each test case, print in a single line a real number accurateup to 3 decimal places, which is the maximum amount of JavaBeansthat FatMouse can obtain.

题目大概翻译:
肥老鼠有M磅猫粮,想要和看守仓库的猫交换他最喜欢的JavaBean。仓库一共有N间,第i间仓库里包含J[i]磅的JavaBeans,想要得到这些JavaBeans需要付出F[i]磅猫粮作为代价。肥老鼠不必得到房间里所有的JavaBeans。他可以用这个房间需要的猫粮数F[i]的a%,来交换这个房间拥有的JavaBeans数J[i]的a%。需要你计算出肥老鼠最多能够得到多少JavaBeans。
输入大概翻译:
输入将包含多组数据,每一组数据将以两个非负整数M
N开始,然后有N行数据,包含两个非负整数J[i]和F[i]。出现两个-1表示测试数据结束。所有的整数都不超过1000
输出大概翻译:
对于每一个测试数据的情况,输出单独的一行(精确到小数点后三位数)来表示这个肥老鼠可以得到的JavaBeans的最大值。

Sample Input:
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
Sample Output:
13.333
31.500

因为本题想要求解的是肥老鼠最后能的得到的最多的JavaBeans的值。所以我们就要尽量可能的在每个房间拿到多的而且便宜的JavaBeans。因此选择贪心算法。

如何界定便宜,不妨换一个想法,也就是性价比,单位重量的猫粮换到的JavaBeans越多就说明越实惠。
基于这个想法,我就想设定一个变量来保存每个房间的实惠情况。同时为了方便对变量进行有效的管理,在这里我选择将一个房间内的需要的猫粮数、拥有的JavaBeans数、以及实惠情况同意储存在一个struct中。

struct food{
int j,f;
double p;
}food_N[MAX];

p表示实惠程度,我选择了用结构数组来表示这个大仓库,每一间小房间就是一个结构体,因为题目中要求每个整数的值都不超过1000因此将整个仓库的大小设置为1000(这样做是使用了food_N[0],如果不想使用food_N[0]数组则需要声明为1001),实惠程度的具体计算方法:

food_N[i].p=(double)food_N[i].j/food_N[i].f;//这里的i表示第i个房间。

在计算出实惠程度之后,因为肥老鼠的目的是得到最多的JavaBeans因此我们需要找出最实惠的房间多换取一点JavaBeans。所以下一步我们需要将实惠程度进行由大到小的排序。首先选择了比较笨拙的冒泡排序法,发现效率一般般的冒泡排序法竟然没有超时,这个让我很惊讶

for(int i=0;i<n;i++)  
        {  
            for(int j=i;j<n;j++)  
            {  
                if(food_N[i].p<food_N[j].p)  
                {  
                    temp=food_N[i];  
                    food_N[i]=food_N[j];  
                    food_N[j]=temp;  
                }  
            }  
        }//这里的n表示总得房间数。

接下来是基于C++的sort排序

sort(food_N,food_N+n,check);

明显代码简洁了很多。
现在实惠程度的排序也已经完成了,可以让肥老鼠去换了,按照实惠程度从最实惠的一个房间开始换走最实惠房间内的所有JavaBeans,依次向下进行,直到自己的猫粮用完。如果出现猫粮不足以完全换走JavaBeans的情况时,本着有多少换多少的原则进行即可。

for(int i=0;i<n;i++)  
        {  
            if(m>food_N[i].f)  
            {  
                sum+=food_N[i].j;  
                m-=food_N[i].f;  
            }  
            else  
            {  
                sum+=food_N[i].p*m;  
                break;  
            }  
        }//这里的m表示肥老鼠拥有的猫粮数目,sum表示肥老鼠可以得到的猫粮总和

一旦肥老鼠的猫粮用完了立刻用break来跳出循环。
本题目的完整代码(冒泡版):

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
struct food{
int j,f;
double p;
}food_N[MAX];

int main(void)
{
int m,n;
while(scanf("%d%d",&m,&n) && (m!=-1 || n!=-1))
{
double sum=0.0;
struct food temp;
for(int i=0;i<n;i++)
{
scanf("%d%d",&food_N[i].j,&food_N[i].f);
food_N[i].p=(double)food_N[i].j/food_N[i].f;
}
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if(food_N[i].p<food_N[j].p)
{
temp=food_N[i];
food_N[i]=food_N[j];
food_N[j]=temp;
}
}
}
for(int i=0;i<n;i++)
{
if(m>food_N[i].f)
{
sum+=food_N[i].j;
m-=food_N[i].f;
}
else
{
sum+=food_N[i].p*m;
break;
}
}
printf("%.3lf\n",sum);
}
return 0;
}

本题完整代码(sort版):

#include <stdio.h>
#include <algorithm>
#define MAX 1000
using namespace std;
struct food{
int j,f;
double p;
}food_N[MAX];
bool check(struct food n,struct food m);

int main(void)
{
int m,n;
while(scanf("%d%d",&m,&n) && (m!=-1 || n!=-1))
{
double sum=0.0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&food_N[i].j,&food_N[i].f);
food_N[i].p=(double)food_N[i].j/food_N[i].f;
}
sort(food_N,food_N+n,check);
for(int i=0;i<n;i++)
{
if(m>=food_N[i].f)
{
sum+=food_N[i].j;
m-=food_N[i].f;
}
else
{
sum+=food_N[i].p*m;
break;
}
}
printf("%.3lf\n",sum);
}
return 0;
}
bool check(struct food n,struct food m)
{
return n.p>m.p;
}

 

发表评论

您的电子邮箱地址不会被公开。