信息学集训队作业_第1页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、挑剔的美食家 Alex Schwendner, 2007 与很多奶牛一样，Farmer John那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在，Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1 = N = 100,000)头挑剔的奶牛。 所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1 = A_i = 1,000,000,000)，并且鲜嫩程度不能低于B_i(1 = B_i = 1,000,000,000)。商店里供应M(1 = M = 100,000)种不同的牧草，第i种牧

2、草的定价为C_i(1 = C_i = 1,000,000,000)，鲜嫩程度为D_i (1 = D_i Dx)的牧草，则有以下两种情况：最终编号为x的牧草没有被取，则不妨让第i头奶牛换成了编号为x的牧草，代价必然减小；第k头奶牛选取了编号为x的牧草。因为第k头奶牛选取了编号为x的牧草，则它同样可以选择编号为y(DyDx)的牧草。此时我们交换第i头奶牛和第k头奶牛的选择，此时方案并未变差。综上可得，按照上述取法取出的方案是最优方案。由于本题的数据范围比较大，因此为了完成上述的贪心过程，我们需要一种能够高效地支持插入、删除、以及找到一个最小的大于等于某个给定元素这三种操作的数据结构，而一棵平衡二叉树则已经完全能够胜任上述的操作。由于对于平衡树来说每一种操作所需要的时间复杂度均为O(logn)，所以这题总的时间复杂度为O(nlogn)，已经足以通过本题官方的全部数据。但是如果我们精益求精，那么我们可以首先将牧草按价格进行离散化，并用一

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论