菜单

贪心法小关卡-洛谷试炼场 贪心法(一)

十月 28, 2018 - 教程系列, 算法

前言

最近工作室开了算法组,要求记录自己的学习历程,也正好找个理由重新开始回坑写博客QAQ,第一周是贪心和搜索,正好拿洛谷做试炼场,顺带把题解写一下好了。这里是第一弹,四道比较简单的问题,之后会有第二弹,有三道稍微有点难度的问题。

第一题 P1090-合并果子

题目描述

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 n−1 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ,并且已知果子的种类 数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。
例如有 3 种果子,数目依次为 1 , 2 , 9 。可以先将 1 、 2 堆合并,新堆数目为 3 ,耗费体力为 3 。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12 。所以多多总共耗费体力 =3+12=15 。可以证明 15为最小的体力耗费值。

Input

共两行。
第一行是一个整数n(1$\leq$n$\leq$10000),表示果子的种类数。
第二行包含n个整数,用空格分割,第i个整数$a_{i}(1\leq a_{i}\leq 20000)$是第i种果子的数目。

Output

一个整数,也就是最小的体力耗费值。输入数据保证这个值小于$2^{31}$.

Sample Input

3
1 2 9

Sample Output

15

题目分析

洛谷几乎都是中文题目,对于直接的题意理解问题不大,拿到这个题最直观的的想法就是:为了保证体力消耗最小,就是先把整个数组排序之后再一个一个累加,这样第一个和第二个数字会被计算(n-1)次,第三个会被计算(n-2)次,知道第n个数字只被计算一次,这样一个公式就求出了结果。但是这个想法是错误的!
为什么错误呢?因为对于整个有序的数组来说,我们这样运算并不能保证一直都是最优解,举个例子:

对于 1 4 4 5 7 9这组数据,当我们把前两个数字合并之后,实际上相当于少了两堆果子,多了一堆新的果子,序列会变成5 4 5 5 7,而对于这个序列,最有解显然不是按这个顺序相加,应该要把这个序列重新排序再进行合并。

于是我们又有了一个思路,每次合并之后对于整个序列再次排序,这样每一次合并就重新排列一次得到的结果一定是正确的。但是我们又会面临时间的问题,事实上这样也确实会TLE。
所以在这里我的处理是每次合并之后,找到一个合适的位置,把这个元素插入序列,再进行下一次合并操作。这也是这个题的正确做法。

代码实现

第二题-P1181

题目描述

对于给定的一个长度为N的正整数序列$A_{i}$,现要将其分成连续的若干段,并且每段和不超过M(可以等于M),问最少能将其分成多少段使得其满足要求。

Input

第1行包含两个正整数N,M表示了数列$A_{i}$的长度与每段和的最大值,第2行包含N个空格隔开的非负整数$A_{i}$,如题目所述。

Output

一个正整数,输出最少划分的段数。

Sample Input

5 6
4 2 4 5 1

Sample Output

3

题目分析

这一题倒是没什么玄机,因为顺序不能改变,所以就是顺着一个一个往后加,超过了就算一组计数就可以,代码也不长。

代码实现

第三题 P1208-混合牛奶(快乐的牛奶商)

题目描述

由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案.
Marry乳业从一些奶农手中采购牛奶,并且每一位奶农为乳制品加工企业提供的价格是不同的。此外,就像每头奶牛每天只能挤出固定数量的奶,每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。
给出Marry乳业每天对牛奶的需求量,还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。
注:每天所有奶农的总产量大于Marry乳业的需求量。

Input

第 1 行共二个数值:N,(0<=N<=2,000,000)是需要牛奶的总数;M,$(0\leq M\leq5,000)$是提供牛奶的农民个数。
第 2 到 M+1 行:每行二个整数:Pi 和 Ai。
$P_{i}(0\leq Pi \leq 1,000)$是农民 i 的牛奶的单价.
$A_{i}(0\leq Ai \leq 2,000,000)$是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。

Output

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

Sample Ipnput

100 5
5 20
9 40
3 10
8 80
6 30

Sample Output

630

题目分析

这道题是一道很经典的贪心法的问题,之前在西电C语言上机课的时候做过一道几乎一模一样的问题叫做快乐的的牛奶商,可能就是同一道题的不同译本吧2333333。
这一题的思路就是让花费尽可能少,也就是尽可能买单价便宜的牛奶,所以我们首先建立一个结构体存储单价和数量,我们要做的就是对单价排序,再从小到大遍历到我们需要的数量为止。
要注意的一点是在我们遍历的时候不能一个一个牛奶遍历,而应该一个一个商人遍历,超过之后再减去多余的,这样会少算很多次。

代码实现

第四题 P1223-排队接水

题目描述

有n个人在一个水龙头前排队接水,假如每个人接水的时间为Ti,请编程找出这n个人排队的一种顺序,使得n个人的平均等待时间最小。

Input

输入文件共两行,第一行为n;第二行分别表示第1个人到第n个人每人的接水时间T1,T2,…,Tn,每个数据之间有1个空格。

Output

输出文件有两行,第一行为一种排队顺序,即1到n的一种排列;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位).

Sample Input

10
56 12 1 99 1000 234 33 55 99 812

Sample Output

3 2 7 8 1 4 9 6 10 5
291.90

题目分析

其实这道题就是简化版的第一题,因为一旦确定排序顺序就不能更改顺序,所以我们要做的真的只是把输入的序列排序输出,就是答案对应的序列。
至于时间的算法,就是先把整个数组排序之后再一个一个累加,这样第一个和第二个数字会被计算(n-1)次,第三个会被计算(n-2)次,直到第n个数字只被计算一次,这样一个公式就求出了结果。(也就是第一题的错误解法233333)

代码实现

标签:, ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注