当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

USACO Mixing Milk 题解

发表于: 2013-04-26   作者:bbsunchen   来源:转载   浏览次数:
摘要: 题目大意:     描述 由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。 Marry乳业从一些奶农手中采购牛奶,并且每一位奶农为乳制品加工企业提供的价格是不同的。此外,就像每头奶牛每天只能挤出固定数量的奶,每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整

题目大意:

 

 

描述

由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。

Marry乳业从一些奶农手中采购牛奶,并且每一位奶农为乳制品加工企业提供的价格是不同的。此外,就像每头奶牛每天只能挤出固定数量的奶,每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。

给出Marry乳业每天对牛奶的需求量,还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。

注:每天所有奶农的总产量大于Marry乳业的需求量。

格式

PROGRAM NAME: milk

INPUT FORMAT:file milk.in

第 1 行共二个数值:N,(0<=N<=2,000,000)是需要牛奶的总数;M,(0<= M<=5,000)是提供牛奶的农民个数。

第 2 到 M+1 行:每行二个整数:Pi 和 Ai

Pi(0<= Pi<=1,000) 是农民 i 的牛奶的单价。

Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。

OUTPUT FORMAT:file milk.out

单独的一行包含单独的一个整数,表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用

 

以上内容来自NOCOW

 

这一题太明显的贪心了,然后把价格排序就可以了。那排序呢,STL提供了map可以完美兼容这种操作,当然网上也有用struct自己来实现的,我要说,效率不一定高嘛,因为印象中map是用堆排序来实现的

 

但是这一题真的卡住了一下,因为map在重复键值的情况下是不能插入的,哦,insert,所以当农民的价格相等时,如果不加判断,就会出错的!

 

下面是可以通过的源码:

/*
ID: bbsunch2
PROG: milk
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <map>

using namespace std;

int main()
{
    ofstream fout ("milk.out");
    ifstream fin ("milk.in");
    map<int, int> price_farmerAmount;

    int totalAmount = 0;
    int farmerNum = 0;
    int totalPrice = 0;

    fin >> totalAmount >> farmerNum;

    for(int i = 0; i < farmerNum; i++)
    {
        int price;
        int farmerAmount;
        fin >> price >> farmerAmount;
        pair<map<int,int>::iterator,bool> ret = price_farmerAmount.insert(pair<int, int>(price, farmerAmount));
        if(!ret.second)
        {
            ret.first->second += farmerAmount;
        }
    }

    map<int, int>::iterator it;

    for( it = price_farmerAmount.begin(); it != price_farmerAmount.end(); it++)
    {
        int price = it->first;
        int farmerAmount = it->second;

        if(totalAmount > farmerAmount)
        {
            totalPrice = totalPrice + price * farmerAmount;
            totalAmount -= farmerAmount;
        }else
        {
            totalPrice = totalPrice + price * totalAmount;
            break;
        }
    }

    fout << totalPrice << endl;
    return 0;
}

 

 

有人问为什么要维护USACO题解这个系列,因为,USACO是不会帮你保存源码的,骚年

 

这一题有个很trick的技巧,也是USACO给出的题解,就是排序可以再O(n)复杂度下完成,因为这个排序满足count sort(计数排序)的条件,在算法导论的第八章有描述,非常简单。

而说到计数排序,就不得不谈谈排序算法的稳定性问题选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。具体分析参考百度即可。

 

USACO Mixing Milk 题解

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
【问题描述】 据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出
题意分析: 给出4个长方形的高和长,以及给出6种基本布局,求合成无重叠的最小面积时的长和宽。 解题
当产品相对稳定与可控,小神有愿望快速记录这个项目。 内容涉及小神参与产品设计与执行的过程,由交
这道题目,给你一组时间范围,求最大的时间跨度和最大的时间段间隔。题目看似挺简单,但是如果不加
我知道写这东西挺二,可是我确实被USACO的提交折腾了很久…… 首先,它的 TEXT Submitting Solution
Shaping Regions N opaque rectangles (1 <= N <= 1000) of various colors are placed on a
上週在「屬於你的另類技巧?10個數位工具創意利用心得」一文中,提到我目前還是以「Remember the mi
柴米油鹽醬醋茶這些生活必需品總是要我們定期去做一番採買,但一長串購物清單如果沒有事先管理,難
【描述】 给定4个矩形块,找出一个最小的封闭矩形将这4个矩形块放入,但不得相互重叠。所谓最小矩形
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号