• 了解贪心算法的概念
  • 学习使用贪心算法结构
  • 学习敲写贪心算法的代码

编程单词

1. greedy[ˈɡriːdi]贪婪的; 贪心的;  
2. algorithm[ˈælɡərɪðəm]算法;

教学内容

  1. 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

  2. 讲解经典题目国王游戏，熟悉常见贪心策略

​

课堂练习

国王游戏代码：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N =1e6+5;
PII a[N];

vector <int> mul(vector <int> a,int b){	
	vector <int> c;
	int t=0;
	for(int i=0;i<a.size();i++){
		t+=a[i]*b;
		c.push_back(t%10);
		t/=10;
	}
	while(t) c.push_back(t%10),t/=10;
	
	return c;
}
vector <int> div(vector <int> a,int b){
	vector <int> c;
	int t=0,x;
	bool is_first=false;
	for(int i=a.size()-1;i>=0;i--){
		t=t*10+a[i];
		x=t/b;
		if(x||is_first){
			is_first=true;
			c.push_back(t/b);	
		}
		t=t%b;
	}
	reverse(c.begin(),c.end());
	
	return c;
}
vector <int> max_vec(vector <int> a,vector <int> b){
	if(a.size()>b.size()) return a;
	if(a.size()<b.size()) return b;
	if(vector <int> (a.rbegin(),a.rend()) > vector <int> (b.rbegin(),b.rend())) return a;
	return b;
	
}

void output(vector <int> a){
	for(int i=a.size()-1;i>=0;i--) cout<<a[i]; 
	cout<<endl;
	return ;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	for(int i=0;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		a[i].x*=a[i].y;
	} 
	sort(a+1,a+1+n);
//	int pre=1,ans=0;
	vector <int> pre(1,1);
	vector <int> ans(1,0);
	for(int i=0;i<=n;i++){
		if(i)ans=max_vec(ans,div(pre,a[i].y));
		pre=mul(pre,(a[i].x/a[i].y));
	}
	output(ans);

	return 0;
}

作业：旅行家的预算

提示:

  • 先局部化想想就除去起点终点就一个加油站的情况该如何选择，两个又该如何选择
  • 根据局部情况所想的策略推广到整体

代码：

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
62
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e6+5;
struct node{
	double s,v;
}a[N];
bool cmp(node a,node b){
	return a.s<b.s;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	double d1,c,d2,p;
	int n;
	cin>>d1>>c>>d2>>p>>n;
	a[0]={0,p};
	for(int i=1;i<=n;i++){
		cin>>a[i].s>>a[i].v;
	}
	a[n+1]={d1,0.0};
	sort(a,a+n+2,cmp);
	double maxx=c*d2,st=0,ans=0;
	int now=0;
	while(st<d1){
		double minn=0x3f3f3f3f;
		int tmp=now,index=0;
		int flag=0;
		for(int i=now+1;i<=n+1;i++){
			if(a[i].v<a[now].v&&(a[i].s-st)<=maxx){
				flag=1;
				ans+=(a[i].s-st)/d2*a[now].v;
				now=i;
				break;
			}
			if(a[i].v<minn&&(a[i].s-st)<=maxx){
				flag=2;
				minn=a[i].v;
				index=i;
			}
		}
		if(flag==1){
			st=a[now].s;
		}
		else if(flag==2){
			now=index;
			st+=maxx;
			ans+=a[tmp].v*c;
		}
		else{
			cout<<"No Solution";
			return 0;
		}
	}
	
	cout<<fixed<<setprecision(2)<<ans;


	return 0;
}