正文

HDU1009_FatMouse' Trade【贪心】【水题】

IP云
IP云V管理员/1 阅读
11/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示
FatMouse' Trade


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 44470    Accepted Submission(s): 14872

Problem Description

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.



Input

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.



Output

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.



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



Author

CHEN, Yue



Source

ZJCPC2004

题目大意：有N个房间，每一个房间存有FatMouse喜欢吃的食物。可是每一个房间

的食物都须要用对应的猫粮去换。

FatMouse 有M磅的猫粮，为它最多能换到多

少的食物。

思路：贪心方法。用结构体存每间房间的食物量和所需猫粮量。

按食物的单位价格（

即食物/猫粮的大小）进行排列，每次选单位价格最小的购买，知道M磅猫粮用完 

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct warehouse

{

    double j;

    double f;

}a[1100];

bool cmp(warehouse a,warehouse b)

{

    return a.f/a.g < b.f/b.g;

}

int main()

{

    int N;

    double M;

    while(~scanf("%lf%d",&M,&N)&& (M!=-1||N!=-1))

    {

        memset(a,0,sizeof(a));

        for(int i = 0; i < N; i++)

        {

            scanf("%lf%lf",&a[i].j,&a[i].f);

        }

        sort(a,a+N,cmp);

        double sum = 0;

        for(int i = 0; i < N; i++)

        {

            if(M <= 0.000001)

                break;

            if(M >= a[i].f)

            {

                sum += a[i].j;

                M -= a[i].f;

            }

            else

            {

                sum += M*a[i].j/a[i].f;

                M = 0;

            }

        }

        printf("%.3lf\n",sum);

    }

    return 0;

}

HDU1009_FatMouse&#39; Trade【贪心】【水题】的更多相关文章
  1. LightOJ 1166 Old Sorting 置换群 或 贪心 水题

    LINK 题意:给出1~n数字的排列,求变为递增有序的最小交换次数 思路:水题.数据给的很小怎么搞都可以.由于坐标和数字都是1~n,所以我使用置换群求循环节个数和长度的方法. /** @Date : ...

  2. DP+贪心水题合集_C++

    本文含有原创题,涉及版权利益问题,严禁转载,违者追究法律责任 本次是最后一篇免费的考试题解,以后的考试题目以及题解将会以付费的方式阅读,题目质量可以拿本次作为参考 本来半个月前就已经搞得差不多了,然后 ...

  3. 【COGS】714. USACO 1.3.2混合牛奶（贪心+水题）

    http://cojs.tk/cogs/problem/problem.php?pid=714 在hzwer的刷题记录上,默默地先跳过2题T_T...求凸包和期望的..T_T那是个啥..得好好学习 看 ...

  4. Gym 101873K - You Are Fired - [贪心水题]

    题目链接:http://codeforces.com/gym/101873/problem/K 题意: 现在给出 $n(1 \le n \le 1e4)$ 个员工,最多可以裁员 $k$ 人,名字为 $ ...

  5. HDU 4334——Trouble——————【贪心&水题】

    Trouble Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Su ...

  6. 2111 ACM 贪心 水题

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=2111 题意:知道背包容量和物品单价.体积.问能买到的最大价值? 注意:单价指的是单位体积的价格 思路:先把 ...

  7. Ride to Office（贪心水题）

    [题目链接] http://noi.openjudge.cn/ch0406/2404/ [算法] 一开始zz了,先按时间排序然后如果速度超过当前男主速度,且在男主到达目的地前超过男主则最终男主和这个人 ...

  8. hdu 1051:Wooden Sticks（水题，贪心）

    Wooden Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Tot ...

  9. 【UOJ#82】【UR #7】水题生成器（贪心）

    [UOJ#82][UR #7]水题生成器(贪心) 题面 UOJ 题解 把\(n!\)的所有约数搜出来,这个个数不会很多. 然后从大往小能选则选就好了. #include<iostream> ...

随机推荐
  1. 【bzoj3513】[MUTC2013]idiots FFT

    题目描述 给定n个长度分别为a_i的木棒,问随机选择3个木棒能够拼成三角形的概率. 输入 第一行T(T<=100),表示数据组数. 接下来若干行描述T组数据,每组数据第一行是n,接下来一行有n个 ...

  2. kb-07专题线段树-02--单点修改，区间最值

    /* 区间单点该值,区间查询最大值: hdu-1754 */ #include<iostream> #include<cstdio> #include<cstring&g ...

  3. LineageOS源码定制手机系统

    LineageOS源码定制手机系统 导语: 现在市场的手机基本就两种:  苹果机和android机. 今天我们不谈苹果机, 对小编我来讲,那是个奢侈品, android是我的最爱.对于一般androi ...

  4. d3 画简单的柱形图

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title> ...

  5. FZOJ 2102 Solve equation

    ...

  6. Codevs 3287 货车运输 == 洛谷P1967

    3287 货车运输 2013年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description A 国有 n 座城市,编 ...

  7. Install Battery Historian

    1. Recommended extra packages for Trusty 14.04 $ sudo apt-get update $ sudo apt-get install \ linux- ...

  8. Delphi 从PaintBox拷贝一部分内容到TBitmap

    将指定的TPaintBox内容(假如为paintbox1)拷贝到一个TBitmap(如Bitmap),可以这么做 Bitmap.Width := PaintBox1.Width; Bitmap.Hei ...

  9. POJ 3368.Frequent values-处理数据+RMQ(ST)

    昨天写的博客删了,占坑失败,还是先把RMQ玩的6一点再去搞后面的东西.废话少说,题解题姐姐_(:з」∠)_      Frequent values Time Limit: 2000MS   Memo ...

  10. jQuery实现tab选项卡效果小demo

    html页面: <section> <h2>Section Title</h2> <ul class="tab-nav"> < ...

相关阅读

目录[+]