Fork me on GitHub

贪心算法

从这篇博客开始,我以后将会在博客上面记录一些 我个人的算法学习经历

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 floating-point 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

1
2
3
4
5
1.00
3.71
0.04
5.19
0.00

Sample Output

1
2
3
4
3 card(s)
61 card(s)
1 card(s)
273 card(s)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
float a=2,b;
float S;
float num;
while(cin>>num,num)
{
while(1)
{
S+=1/a;
if(S>=num) break;
else a++;
}
cout<<a-1<<" card(s)"<<endl;
S=0;a=2;
}
return 0;
}

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 space-separated 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

    1
    2
    3
    4
    3 10
    1 7
    3 6
    6 10

Sample Output

1
2

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)也是可以的,

上代码之前先讲一个操作,对结构体里面的数据进行排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct cow
{
int x;
int y;
}q[maxn];
bool cmp(const cow &qaq,const cow &wow)//对结构数组根据x进行升序排列。
{
return qaq.x<wow.x;//相当于对结构体里面的数据x进行了升序排序。
}
//如果x相同在对y进行排序写个if就可以了。
//bool cmp(const cow &qaq,const cow &wow)
{
if(qaq.x==wow.x) return qaq.y<wow.y;
return qaq.x<wow.x;
}
调用的时候用sort(q,q+n,cmp)就可以完成我们想要的排序啦。开心.jpg。

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
int cnt=1;//从第一头牛开始找起。
const int maxn=1000000;
using namespace std;
struct cow
{
int x;
int y;
}q[maxn];
bool start(const cow &qaq,const cow &wow)//对结构数组根据x进行升序排列。
{
return qaq.x<wow.x;
}
/*bool finsh(const cow &qaq,const cow &wow)//对结构数组根据y进行升序排列。
{
return qaq.y<wow.y;
}
*/
int main()
{
int n,T;
while(cin>>n>>T)
{
for(int i=0;i<n;i++)
{
cin>>q[i].x>>q[i].y;
}
sort(q,q+n,start);//根据开始时间进行排序。
int cnt=0,temp=0;
bool flag=0;
for(int i=0;i<n;)
{
int top=temp;
if(temp+1<q[i].x)
{
break;//如果最开始的时间1都覆盖不到,直接GG。
}
while(i<n&&temp+1>=q[i].x)//由于是开区间所以上一个的结束时间要+1
{
top=top>q[i].y?top:q[i].y;//让top等于最大的结束时间。
i++;
}
cnt++;//找到一头奶牛后,计数器加个1。
temp=top;//为下一次循环准备。
if(temp==T)
{
flag=1;
break;
}
}
if(flag)
{
cout<<cnt<<endl;
}
else cout<<"-1"<<endl;
}
return 0;
}

D - Yogurt factory

The cows have purchased a yogurt factory that makes world-famous 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 well-designed, 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 N-week 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 space-separated integers, N and S.

  • Lines 2..N+1: Line i+1 contains two space-separated 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 32-bit integer.

    Sample Input

    1
    2
    3
    4
    5
    4 5
    88 200
    89 400
    97 300
    91 500

Sample Output

1
126900

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.

题目分析

这个题目可以说是里面很水的一个了。
贪心策略是比较简单的。就是比较牛奶是储存花费的钱少还是把牛奶当天制造出来花费的钱少(可能我翻译的有点问题)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int minc=0x3f3f3f3f//把定义为无穷大,
int main()
{
long long n,s;
cin>>n>>s;
long long sum=0;
while(n--)
{
long long c,y;
cin>>c>>y;
c=min(c,minc+s);
minc=c;
sum+=c*y;
}
cout<<sum<<endl;
return 0;
}
-------------本文结束感谢您的阅读-------------