从这篇博客开始，我以后将会在博客上面记录一些 我个人的算法学习经历
By acmclub 吴东
反省
我承认自己真的学习能力挺差的，经常忘记很多东西，算法学习了又容易健忘。笔记本上抄了算法，但发现笔记本太小，笔也写不完，因而我决定开始一段博客之路，来记录我的算法之路。
贪心介绍
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
直接从我们这周的算法题开始讲解吧。
这周由于考试和给计工学院写题解，并没有怎么去写算法题。但好在榜单的ac题目很明显，于是我成功找到了几个比较水的题目。
题目
A  Hangover
How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We’re assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + … + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.
Input
The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floatingpoint number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.
Output
For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.
Sample Input


Sample Output


这道题目，我看不出半点贪心思维亦或是算法的搞头。于是我把他当当成了一篇4级英语阅读文章来看了下。一个循环就可以解决了。
直接上我的ac代码。


B  Cleaning Shifts
Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.
Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.
Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print 1.
Input
Line 1: Two spaceseparated integers: N and T
Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.
Output Line 1: The minimum number of cows Farmer John needs to hire or 1 if it is not possible to assign a cow to each shift.
Sample Input
12343 101 73 66 10
Sample Output


Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
INPUT DETAILS:
There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.
OUTPUT DETAILS:
By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.
分析
这个题目，并没有什么英语语法的难度，顶多几个生词，自己猜一下题目意思很快就出来了。
我翻译的题目大致意思就是让最少的奶牛的清洁时间去覆盖题目所给的区间，这题目挺违背常识的（奶牛还能做清洁？？？666），emmm 分析题目吧，要用最少的牛去覆盖所有区间，可以说是一道很典型的贪心题目了。这道题目我自己也思考了很久，觉得挺有意思的。
我个人的思路是这样的：先对每个奶牛依据开始清洁时间进行从小到大的一个排序，然后用一个循环遍历找结束时间最晚的奶牛。每次换一次最大值，再次进行遍历，直到把牛遍历完抑或是最大的时间等于T为止。
要注意这个题目，是个开区间，也就是说覆盖10的话（1,3）（4，6）（7,10）也是可以的，
上代码之前先讲一个操作，对结构体里面的数据进行排序：


代码实现如下：


D  Yogurt factory
The cows have purchased a yogurt factory that makes worldfamous Yucky Yogurt. Over the next N (1 <= N <= 10,000) weeks, the price of milk and labor will fluctuate weekly such that it will cost the company C_i (1 <= C_i <= 5,000) cents to produce one unit of yogurt in week i. Yucky’s factory, being welldesigned, can produce arbitrarily many units of yogurt each week.
Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of S (1 <= S <= 100) cents per unit of yogurt per week. Fortuitously, yogurt does not spoil. Yucky Yogurt’s warehouse is enormous, so it can hold arbitrarily many units of yogurt.
Yucky wants to find a way to make weekly deliveries of Y_i (0 <= Y_i <= 10,000) units of yogurt to its clientele (Y_i is the delivery quantity in week i). Help Yucky minimize its costs over the entire Nweek period. Yogurt produced in week i, as well as any yogurt already in storage, can be used to meet Yucky’s demand for that week.
Input
Line 1: Two spaceseparated integers, N and S.
Lines 2..N+1: Line i+1 contains two spaceseparated integers: C_i and Y_i.
Output Line 1: Line 1 contains a single integer: the minimum total cost to satisfy the yogurt schedule. Note that the total might be too large for a 32bit integer.
Sample Input
123454 588 20089 40097 30091 500
Sample Output


Hint
OUTPUT DETAILS:
In week 1, produce 200 units of yogurt and deliver all of it. In week 2, produce 700 units: deliver 400 units while storing 300 units. In week 3, deliver the 300 units that were stored. In week 4, produce and deliver 500 units.
题目分析
这个题目可以说是里面很水的一个了。
贪心策略是比较简单的。就是比较牛奶是储存花费的钱少还是把牛奶当天制造出来花费的钱少（可能我翻译的有点问题）。
代码实现

