`
bbsunchen
  • 浏览: 234767 次
  • 性别: Icon_minigender_1
  • 来自: 天朝帝都
社区版块
存档分类
最新评论

USACO Mixing Milk 题解

阅读更多

题目大意:

 

 

描述

由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助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(计数排序)的条件,在算法导论的第八章有描述,非常简单。

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

 

0
3
分享到:
评论

相关推荐

    Usaco总结&题解

    1. **更复杂的贪心算法应用**:例如题目《Mixing Milk》,除了基础的贪心策略外,还需要考虑如何有效地实现这些策略。 2. **搜索算法的深入应用**:例如题目《The Clocks》,可能需要结合搜索算法和剪枝技巧来求解。...

    USACO2001-2007历年月赛测试数据+题目+题解打包全

    资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。

    SD规范 SDIO规范(全套规范)

    1 PartA2_SD Host_Controller_Simplified_Specification_Ver4.20 2 PartA2_SD_Host_Controller_Simplified_Specification_Ver2.00 3 PartE1_SDIO_Simplified_Specification_Ver2.00 4 PartE1_SDIO_Simplified_Specification_Ver3.00 5 Part1 PhysicalLayerSimplifiedSpecificationVer9.10Fin_20231201 6 PartE7_Wireless_LAN_Simplified_Addendum_Ver1.10 7 Part1_Extended_Security_Simplified_Addendum_Ver1.00 8 Part1_NFC_Interface_Simplified_Addendum_Ver1.00 9 Part1_UHS-II_Simplified_Addendum_Ver1.02 10 PartA1_ASSD_Extension_Simplified_Specification_Ver2.00 11 PartE2_SDIO Bluetooth_Type_A_Simplified_Specification_Ver1.00 12 SDUC-Host-Implementation-Guideline_Ver1.00

    元宇宙的未来:沉浸式互联网解锁万亿社交经济

    《步入元宇宙》由马克·范·里门撰写,是一本深入探讨元宇宙概念、历史、现状以及未来潜力的书籍。作者从Web 1.0到Web 3.0的发展讲起,详细分析了从增强现实(AR)到虚拟现实(VR)再到扩展现实(XR)的技术演进。书中提出了元宇宙的六大特征:互操作性、去中心化、持久性、空间性、社区驱动和自我主权,并强调了开放元宇宙的重要性及其带来的自由和创新潜力。作者还探讨了元宇宙对个人身份、商业、教育、娱乐等领域的深远影响,并预测了元宇宙将如何推动形成一个全新的社交经济。书中引用了多位行业专家的评价,强调了无论读者对元宇宙的了解程度如何,都能从中获得新的见解和启发。

    MW6S004的ads模型

    卢益峰ads仿真放大器章节所需的ads库和MW6S004的ads模型

    javaSE阶段面试题

    javaSE阶段面试题

    《网页制作基础教程(Dreamweaver-CS6版)》第10章-网站的管理与上传.pptx

    《网页制作基础教程(Dreamweaver-CS6版)》第10章-网站的管理与上传.pptx

    Abaqus双线盾构隧道超精细模型构建:涵盖软化模量与盾构注浆关键技术

    内容概要:本文详细介绍了如何使用Abaqus软件构建双线盾构隧道的超精细模型,特别是针对隧道间的联络通道、软化模量和盾构注浆等关键要素进行了深入探讨。文章首先阐述了模型的整体架构搭建,包括使用Python脚本创建隧道衬砌部件。接下来,讨论了软化模量的引入及其在材料本构模型中的定义方式,展示了如何通过塑性应变来模拟软化模量的变化。此外,文章详细讲解了盾构注浆的模拟方法,如通过单元生死技术激活注浆体单元,并提供了具体的Python代码示例。最后,文章强调了网格划分、接触设置等方面的注意事项,确保模型能够稳定运行并获得精确的结果。 适合人群:从事隧道工程数值模拟的研究人员和技术人员,尤其是熟悉Abaqus软件的工程师。 使用场景及目标:适用于需要进行双线盾构隧道工程力学行为研究的场合,旨在帮助工程师更好地理解和预测隧道施工过程中可能出现的问题,从而优化设计方案,提高施工效率和安全性。 其他说明:文中提供的代码片段和建模技巧基于作者的实际经验和测试结果,对于初学者而言,建议逐步尝试每个步骤并在实践中不断调整参数以适应具体工程项目的需求。

    《自然资源信息化时代背景与发展》.pdf

    《自然资源信息化时代背景与发展》.pdf

    《网络社会学(第2版)》15-网络社会变迁.ppt

    《网络社会学(第2版)》15-网络社会变迁.ppt

    西门子1214PLC与KTP700触摸屏构建双相机四轴多工位检测系统的实战案例

    内容概要:本文详细介绍了使用西门子1214PLC和KTP700Basic PN触摸屏构建双相机四轴多工位检测设备的具体实现方法。主要内容涵盖硬件配置、程序主体功能及其代码解析、触摸屏功能实现等方面。硬件方面,采用了西门子1214PLC作为核心控制器,KTP700Basic PN触摸屏为人机界面,双相机用于检测,第三设备通过Modbus RTU通讯。程序主体功能包括上下双工位4轴脉冲控制步进电机、与上位机双相机的TCP/IP通讯、与第三设备的Modbus RTU通讯。触摸屏功能则涉及多重画面、配方管理和密码保护等功能。文中还分享了一些调试经验和注意事项,如轴使能信号要用上升沿触发、相机通讯需配置心跳包机制等。 适合人群:从事工业自动化领域的工程师和技术人员,特别是那些对PLC编程、触摸屏应用和多工位检测设备感兴趣的读者。 使用场景及目标:适用于需要构建复杂自动化检测系统的工程项目,旨在提高检测效率和准确性,确保设备稳定可靠运行。通过学习本文,读者能够掌握如何使用西门子1214PLC和KTP700触摸屏搭建类似的检测系统。 其他说明:文中提供了大量具体的代码示例和调试技巧,有助于读者更好地理解和实施相关技术。此外,还强调了实际工程中常见的问题及解决方案,如接线和接地问题、通讯参数配置等。

    官方emmc规范(多个版本)

    - **4.4 版本** - 介绍了基础特性和标准,适合初学者了解eMMC的基本框架。 - **4.41 版本** - 对4.4版进行了修订和完善,优化了部分规范以适应市场和技术的发展。 - **4.5 版本** - 引入了新的性能改进和技术特性,进一步提升了存储效率。 - **4.51 版本** - 包含针对4.5版的小幅修正和增强,确保技术规范的准确性和实用性。 - **5.0 版本** - 重大更新,引入更多高级功能,支持更高的数据传输速率,对现代高性能需求进行了响应。 - **5.01 版本** - 在5.0基础上的维护更新,保持标准的一致性和先进性。 - **5.1 版本** - 最新的公开版本之一,提供了更全面的标准规范,加强了数据管理能力,提升了可靠性

    DeepSeek系列-提示词工程和落地场景.pdf

    DeepSeek系列-提示词工程和落地场景.pdf

    JDK(java)安装及配置

    JDK(java)安装及配置

    引力搜索算法(GSA)的MATLAB实现及其应用解析

    内容概要:本文详细介绍了引力搜索算法(Gravitational Search Algorithm, GSA)的原理、MATLAB实现及其应用场景。首先解释了GSA的基本概念,即将优化问题中的候选解视为宇宙中互相吸引的粒子,通过模拟物理现象进行优化。接着展示了核心的粒子运动方程,包括加速度计算、质量分配以及引力公式的具体实现。文中提供了多个经典的测试函数如Sphere、Rastrigin等用于验证算法性能,并通过动态绘图展示了粒子群的收敛过程。此外,讨论了算法参数设置的影响,如引力常数G的指数衰减方式,以及如何通过添加随机扰动避免粒子陷入局部最优。最后强调了GSA在解决多峰优化问题方面的优势。 适合人群:对优化算法感兴趣的科研人员、学生及工程师,尤其是那些希望深入了解群体智能算法的人。 使用场景及目标:适用于需要高效寻找全局最优解的问题,特别是在面对复杂的多峰函数时。目标是帮助读者理解GSA的工作机制,掌握其MATLAB实现方法,并能够根据实际情况调整参数以获得更好的优化效果。 其他说明:尽管GSA在低维问题上有出色表现,但在高维优化问题中可能存在效率瓶颈,因此建议进一步研究并行计算或近似邻居搜索等改进措施。

    基于Andorid的跨屏拖动应用设计.zip

    基于Andorid的跨屏拖动应用设计实现源码,主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。

    DeepSeek R1 7b本地部署模型整合包及超全学习教程.rar

    DeepSeek R1 7b本地部署模型整合包及超全学习教程,资源总大小420G,喜欢的自行下载。

    精品推荐-最新人工智能训练师认证题库资料汇总(15份).zip

    精品推荐,最新人工智能训练师认证资料汇总,15份。供大家学习参考。 (新版)人工智能训练师(中级)职业技能等级认定考试题库.pdf 2025年人工智能训练师(高级)职业技能鉴定参考题库(含答案).pdf 阿里认证高级人工智能训练师真题.pdf 初级人工智能训练师题库.pdf 高级人工智能化训练师认证答案解析.doc 高级人工智能训练师.docx 高级人工智能训练师题库.pdf 人工智能技术应用基础课件:人工智能训练师.pdf 人工智能训练师(服务机器人人工智能技术应用)(学生组)理论题库.pdf 人工智能训练师(服务机器人人工智能技术应用)理论题库.docx 人工智能训练师概述课件.pdf 人工智能训练师基础(上册).pdf 人工智能训练师技能等级认定四级理论知识试卷.docx 人工智能训练师试题及答案(150题).pdf 人工智能训练师职业技能标准.pdf

    电力系统优化调度中基于Logistic函数的需求响应建模及其应用

    内容概要:本文探讨了Logistic函数在电力系统优化调度中的应用,特别是用于描述用户对电价变化的响应行为。文中详细介绍了Logistic函数如何通过S型曲线特性,将电价差与负荷转移率关联起来,形成死区、响应区和饱和区三个不同的响应阶段。此外,文章还展示了如何使用MATLAB进行仿真,以及在综合能源系统和微电网中的具体应用案例,如优化分时电价策略、设计需求响应激励机制等。 适合人群:电力系统研究人员、微电网调度工程师、能源管理专业学生。 使用场景及目标:适用于需要理解和应用需求响应模型的研究和工程项目,旨在提高电力系统的经济性和效率,优化调度策略。 其他说明:文章强调了模型的实际应用挑战,如参数调校、异常处理等,并提供了具体的MATLAB代码示例,帮助读者更好地理解和应用Logistic函数模型。

    测试题.docx【C语言教育】C语言考核测试题:涵盖选择题与程序设计题的综合评估系统

    内容概要:本文档是一份C语言考核测试题,分为选择题和程序设计题两大部分。选择题部分共25题,涵盖C语言的基本概念、语法细节、运算符优先级、表达式求值、数据类型转换、控制结构等方面的知识点,旨在考察学生对C语言基础知识的理解与掌握。程序设计题部分提供了多个编程题目,如求数列和、阶乘之和、货币组合方式、质数与完数的求解、日期计算等,侧重于考察学生的实际编程能力和解决问题的能力。 适合人群:适合正在学习或复习C语言的学生,特别是计算机相关专业的本科生或高职高专学生。 使用场景及目标:①作为课堂练习或课后作业,帮助学生巩固所学知识;②作为考试或竞赛的模拟试题,评估学生对C语言的理解程度;③为教师提供教学参考,辅助课程设计与教学计划制定。 其他说明:建议考生在答题过程中仔细阅读题目要求,确保理解每个问题的具体含义。对于程序设计题,应先思考解决方案再动手编写代码,注意代码的规范性和可读性。同时,可以通过实际编译运行来验证程序的正确性。

Global site tag (gtag.js) - Google Analytics