贪心-HDU 1009

描述:

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.

说明:

一共有n个房子,每个房子里有老鼠喜欢吃的javabeans,但是每个房间里的javabeans的价格不一样。老鼠用m元,问m元最多可以卖多少javabeans,其中每个房间里的javabeans可以被分割。

输入:

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.

源码:

#include<stdio.h>
#include <stdlib.h>

//http://acm.hdu.edu.cn/showproblem.php?pid=1009

typedef struct trade_s {
    //注意这里只能是整数
    int javaBean, catFood;
    double normalize;
} trade_t;

static trade_t w[1100];

//用qsort函数必须注意这个函数返回的是int类型,所以这里会返回1和-1
int cmp(const void * x, const void * y) {
    //注意这里直接用减法并且返回1和-1
    return ((trade_t*)x)->normalize - ((trade_t*)y)->normalize > 0 ? -1 : 1;
}

int main() {
    //n是行数,m是总重量
    int n, m, i;
    double sum;

    while (scanf("%d %d", &m, &n)) {
        //输入-1结束
        if (m == -1 && n == -1) break;
        //重置sum
        sum = 0;
        //输入n行数据
        for (i = 0; i <= n - 1; i++) {
            //得到javaBean需要付出catFood
            scanf("%d %d", &w[i].javaBean, &w[i].catFood);
            //计算单价购买量
            w[i].normalize = ((double)w[i].javaBean) / w[i].catFood;
        }
        //排序
        qsort(w, n, sizeof(trade_t), cmp);

        for (i = 0; i < n; i++) {
            //如果支付得起,则购买
            if (m >= w[i].catFood) {
                printf("food %d %d\n", w[i].catFood, w[i].javaBean);
                //增加获得的重量
                sum = sum + w[i].javaBean;
                //减去付出
                m -= w[i].catFood;
            } else {
                //支付不起,以单价购买量乘以重量
                sum = sum + w[i].normalize * m;
                break;
            }
        }
        printf("%.3lf\n", sum);
    }
    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-12-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

44730
来自专栏非著名程序员

这是对付产品经理的一副毒药,程序员慎入

程序员和产品经理的日常就像是一对天生的冤家,为了需求的实现,几乎天天在争吵。这不,就在昨天各大技术和产品群里一个程序员暴打产品经理的视频火了,被广泛传播。

12520
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

22440
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18330
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

30440
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.2K20
来自专栏腾讯大讲堂的专栏

白底黑字or黑底白字,眼睛更喜欢哪一个?

12310
来自专栏非著名程序员

「我真的没有改需求」

12110
来自专栏web前端教室

你可以从面试中学到什么?

讲一下我对面试的一些。。。“偏见”,哈哈,熟悉我的同学们一定要批判的读接下来的内容哈。

12400
来自专栏腾讯NEXT学位

今天我就说三句话

11720

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励