算法题整理——贪心

发表于 | 分类于 |

有时局部最优就是全局最优，当前最好就是最好，这就是贪心

贪心的难点在于什么时候能用，怎么用。其关键在于——局部最优能保证全局最优吗，如何证明

有时候，衡量局部最优并非用最终求解的问题来衡量，可能推导出其它标准——甚至我根本算不出来当前的局部最优解是多少，但我能证明一种状态总比另一种好，因此我能总选用一种状态

CH0701_国王游戏

描述

在国庆日，国王打算玩这样的游戏：国王和大臣们在自己的左右手上各写一个正整数，然后站成一排，国王必定站在最前面，之后，国王会根据这些数字和大臣们站的顺序来赏赐他们。

赏赐的方法是这样的：国王用金币来赏赐大臣，每个人得到的金币个数等于他前面所有人左手上的数字乘积除以他自己右手上的数字。

现在，国王不希望任何一个大臣拿到格外多的赏赐，所以，国王打算在大臣写好数字之后再根据他们手上的数字亲自给他们排队。

已知国王和每个大臣左右手的数字，求得到赏赐最大的大臣获得的最少金币数。

数据范围

大臣数目1 < n < 1000

写在手上的数字1 < a,b < 1e5

思路

如何确定两个大臣的先后顺序？

假设大臣i和j相邻，假设他们得到的赏金是si和sj，那么：

如果i = j + 1，有：

1
2
si = k * l[j] / r[i]
sj = k / r[j]

如果j = i + 1，有：

1
2
sj = k * l[i] / r[j]
si = k / r[i]

其中k是i，j前面的人左手数的乘积，相当于公共项，l，r分别表示左，右手上的数字。

我们假设i在j前面比j在i前面好，那么对于情况1，我们知道需要满足的条件是：

max(k * l[i] / r[j], k / r[i]) < max(k * l[j] / r[i], k / r[j])

简单推导一下逻辑关系，可以得到关键在于：

l[i] / r[j] < l[j] / r[i]

即：

l[i] * r[i] < l[j] * r[j]

那么我们计算出每个大臣左右手数字的积并排序，从小到大的顺序就是最优情况。

大数乘除

这个题恶心的地方在于，它的解是会超过int64的上限的。我们不得不手写一个大数乘法除法。

思路比较简单，用数组模拟即可。

但要把它写对可真不容易啊。

我用long long数组模拟一个大整数，数组每个存4位十进制位。并使用额外的变量来存储其数位。

大整数乘long long型整数的实现：遍历数组每一位都乘一遍long long型整数，然后进位。

除法的实现：额外使用一个变量来存储余数，从最高位开始除，要注意的是余数的维护。

比较大小：先比较长度，再按位比较。

解决

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000 + 5;
const long long M = 1e4;

int n;
long long a, b;
long long l[N], r[N], v[N];
int id[N];

bool cmp(int i, int j){
	return v[i] < v[j];
}

int main(){
	//freopen("input", "r", stdin);
	scanf("%d", &n);
	scanf("%lld %lld", &a, &b);
	for(int i = 0; i < n; ++i){
		scanf("%lld %lld", &l[i], &r[i]);
		v[i] = l[i] * r[i];
		id[i] = i;
	}
	sort(id, id + n, cmp);
	long long maxx[1000];
	long long ret[1000];
	long long temp[1000];
	memset(maxx, 0, sizeof(maxx));
	memset(ret, 0, sizeof(ret));
	memset(temp, 0, sizeof(temp));
	int len = 0;
	int lent = 0;
	int lenm = 0;
	while(a){
		ret[len++] = a % M;
		a /= M;
	}
	for(int i = 0; i < n; ++i){
		int ii = id[i];
		long long div = r[ii];
		long long eta = 0;
		
		lent = 0;
		memset(temp, 0, sizeof(temp));
		
		for(int j = len - 1; j >= 0; --j){
			eta *= M;
			if((ret[j] + eta) / div == 0){
				eta += ret[j];
				continue;
			}
			temp[j] = (ret[j] + eta) / div;
			eta = (ret[j] + eta) % div;
			if(lent == 0) lent = j + 1;
		}
		
		int flag = 0;
		if(lent > lenm) flag = 1;
		else if(lent == lenm){
			for(int j = lent - 1; j >= 0; --j){
				if(temp[j] > maxx[j]){
					flag = 1;
					break;
				}
			}
		}
		
		if(flag){
			lenm = lent;
			for(int j = 0; j < lent; ++j) maxx[j] = temp[j];
		}
		
		for(int j = 0; j < len; ++j){
			ret[j] *= l[ii];
		}
		
		for(int j = 1; j < len; ++j){
			ret[j] += (ret[j - 1] / M);
			ret[j - 1] %= M;
		}
		
		while(ret[len - 1] >= M){
			ret[len] = ret[len - 1] / M;
			ret[len - 1] %= M;
			++len;
		}
		//printf("%d %lld\n", ii, mmax);
	}
	
	if(lenm == 0) printf("0\n");
	else {
		printf("%d", maxx[lenm - 1]);
		for(int i = lenm - 2; i >= 0; --i){
			if(maxx[i] >= 1e3) printf("%lld", maxx[i]);
			else if(maxx[i] >= 1e2) printf("0%lld", maxx[i]);
			else if(maxx[i] >= 1e1) printf("00%lld", maxx[i]);
			else printf("000%lld", maxx[i]);
		}
		printf("\n");
	}
	
	
	return 0;
}

POJ1328_Radar Installation

描述

在平面直角坐标系里，有一些岛屿的坐标（岛屿被看成是一个点）在x轴的上面，现在要在x轴上修建一些雷达，每个雷达的覆盖范围是半径为R的圆形，要求实现对岛屿的雷达全覆盖，问最少修建的雷达数目是多少。

数据范围

岛屿数量1 < n < 1000

思路

对于每个岛屿，我们可以计算出一个范围，使得在这个范围内的任意一个雷达都可以覆盖这个岛屿（勾股定理就可以算出来）。

这样，我们对于每个岛屿的范围的最左点进行排序，然后从左到右进行遍历。我们记录上一个修建的雷达的横坐标是pos，一开始pos是负无穷。

对于每个岛屿，有两个选择：

1.新建一个雷达，覆盖这个岛屿。

2.使用已经有的雷达来覆盖这个岛屿。

我们的策略是：如果可以选择2，那么我们不会选择1。

下面我们证明：

如果我们可以选择2，却新建了一个雷达来覆盖该岛屿。那么我们的雷达只能建在这个岛屿的被管辖范围内。但如果我们调整了已有雷达，那么我们可以新建一个任意位置的雷达，至少也不会比上面的选择差。

所以，对于每个点i，我们看pos能不能移动来覆盖当前的点。

如果pos < l[i]，说明上一个雷达无法覆盖到当前岛屿，我们需要新建一个。我们新建雷达的位置要尽量靠右，使得尽量覆盖后面的岛屿，所以这时有：

pos = r[i]

如果pos > l[i]，说明上一个雷达可以覆盖到当前岛屿，但有一种情况是同时有pos > r[i]说明，上一个雷达太靠右了，我们需要往左移动一点，最小限度的往左移动是移动到r[i]，但是，我们往左移动会不会影响到之前的点呢？我们说不会，因为往左移动的最大限度就是l[i]，但l[i]已经排过序了，再移动也不会移出之前的范围之外。

但我们不能向右移动，因为始终至少有一个岛屿的覆盖范围的右端等于pos，一旦向右移动，这个岛将不会被覆盖到。

解决

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
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1000 + 5;

double x[N], y[N], l[N], r[N];

int ind[N];

bool cmp(int i, int j){
	return l[i] < l[j];
}

int main(){
	int con = 0;
	int n, d;
	scanf("%d %d", &n, &d);
	while(n || d){
		int flag = 0;
		for(int i = 0; i < n; ++i){
			ind[i] = i;
			scanf("%lf %lf", &x[i], &y[i]);
			if(d < y[i]){
				flag = 1;
				continue;
			}
			l[i] = x[i] - sqrt(d * d - y[i] * y[i]);
			r[i] = x[i] + sqrt(d * d - y[i] * y[i]);
			//printf("%lf %lf\n", l[i], r[i]);
		}
		int ret = 0;
		if(flag == 0){
			sort(ind, ind + n, cmp);
			double pos = l[ind[0]] - 1; 
			for(int i = 0; i < n; ++i){
				int id = ind[i];
				if(pos < l[id]){
					pos = r[id];
					++ret;
				}else{
					pos = min(pos, r[id]);
				}
			}
		}
		printf("Case %d: %d\n", ++con, flag ? -1 : ret);
		scanf("%d %d", &n, &d);
	}
	return 0;
}

POJ3190_Stall Reservations

描述

有n头奶牛，它们每头都有一个确定的挤奶时间段。在某头牛的挤奶时间段内，它需要一个牛棚单独挤奶。现在求至少需要的牛棚数目。

数据范围

1 < n < 50000

思路

按照挤奶开始时间对奶牛排序，然后从早到晚地取一头牛，如果在它的挤奶开始时间点有空闲的牛棚，就把它安排到编号最小的牛棚里，如果没有，则为它新建一个牛棚。

下面证明这样的策略一定是需要牛棚最少的：

假设最开始就已经有一定数量的牛棚，数量是m。

对于任意的一个时间点x，每头牛有三种状态：

1.正在被挤奶

2.挤奶完成

3.还未被挤奶

那么对于第i头牛，在它开始需要被挤奶的时间点，所有开始时间比i早的牛只能处于1，2两种状态。

已经处于状态1的牛对第i头牛是没有影响的，显然，处于状态3的牛由于未到开始挤奶时间，对第i头牛也是没有影响的。

对i来说，需要考虑的就是有多少处于状态2的牛，假设有y头，那么，i有m-y个牛棚可以选择。

对第i头牛来说，前面的牛被安排到哪个牛棚实际上是不重要的。因为无论安排到哪个牛棚，前面的牛只要满足其结束时间大于等于第i头牛的开始时间，就一定会占用一个牛棚。

所以i被安排到哪个牛棚，对后面的牛来说也没有影响，唯一有影响的是i的结束时间。

所以我们不妨把i安排到编号最小的牛棚。

实现

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
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 50000;

struct cow{
	int s;
	int e;
} cows[N];

struct stall{
	int e;
	int id;
} stalls[N];

int ind[N];
int rets[N];

bool cmp1(int i, int j){
	return cows[i].s < cows[j].s;
}

struct cmp2{
	bool operator()(stall a, stall b){
		return a.e > b.e;
	}
};

int main(){
	int n, ret = 0, con = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) scanf("%d %d", &cows[i].s, &cows[i].e);
	for(int i = 0; i < n; ++i) ind[i] = i;
	sort(ind, ind + n, cmp1);
	priority_queue<stall, vector<stall>, cmp2> q;
	if(n){
		stall temp;
		temp.id = ++con;
		temp.e = cows[ind[0]].e;
		q.push(temp);
		rets[ind[0]] = 1;
		for(int i = 1; i < n; ++i){
			temp = q.top();
			if(temp.e < cows[ind[i]].s){
				//printf("%d %d\n", temp.e, cows[ind[i]].s);
				q.pop();
				temp.e = cows[ind[i]].e;
				q.push(temp);
			}else{
				temp.id = ++con;
				temp.e = cows[ind[i]].e;
				q.push(temp);
			}
			rets[ind[i]] = temp.id;
		}
	}
	printf("%d\n", q.size());
	for(int i = 0; i < n; ++i) printf("%d\n", rets[i]);
	return 0;
}

POJ3614_Sunscreen

描述

有c头奶牛在晒日光浴，每头都需要涂防晒霜，每种防晒霜有不同的spf数。对于每头奶牛，它们能接受的SPF指数在一个区间[minspf, maxspf]内，现在给出每头奶牛能接受的spf指数区间，每种防晒霜的spf指数和瓶数（防晒霜一共有l种，每头奶牛需要用整整一瓶的防晒霜），求最多能让多少头奶牛晒日光浴（如果没有合适的防晒霜，那么这头奶牛只能放弃晒日光浴了）。

数据范围

1 <= c , l <= 2500

思路

考虑每头奶牛所能接受的最低spf指数，按照最低的spf指数从大到小对奶牛们排序。

然后遍历奶牛，对每头奶牛，在剩下的防晒霜里找到它能用的，且spf指数最高的防晒霜给它用。使用这种策略所能满足的奶牛总数就是最大值。

下面证明：

首先，由于奶牛是按照最低spf指数排序的，那么假设对于奶牛ci来说，有两瓶防晒霜可以用，spf指数分别是x和y，且y>x，那么对于排在ci后面的cj说，只会出现三种情况：能用x，y；不能用x，y；能用x，不能用y；所以ci尽可能地选择spf指数大的防晒霜一定是最优的。

解决

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2500 + 5;

struct lotion{
	int spfs;
	int cover;
} lotions[N];

struct cow{
	int maxspf;
	int minspf;
} cows[N];

bool cmpcow(cow i, cow j){
	if(i.minspf == j.minspf) return i.maxspf > j.maxspf;
	return i.minspf > j.minspf;
}

bool cmplotion(lotion i, lotion j){
	return i.spfs > j.spfs;
}

int main(){
	int c, l;
	scanf("%d %d", &c, &l);
	for(int i = 0; i < c; ++i) scanf("%d %d", &cows[i].minspf, &cows[i].maxspf);
	for(int i = 0; i < l; ++i) scanf("%d %d", &lotions[i].spfs, &lotions[i].cover);
	sort(cows, cows + c, cmpcow);
	sort(lotions, lotions + l, cmplotion);
	
	//for(int i = 0; i < c; ++i) printf("%d %d\n", cows[i].minspf, cows[i].maxspf);
	//for(int i = 0; i < l; ++i) printf("%d %d\n", lotions[i].spfs, lotions[i].cover);
	
	int ret = 0;
	int con = 0;
	for(int i = 0; i < c; ++i){
		int maxlotion_spfs = -1;
		int maxpos = -1;
		for(int j = 0; j < l; ++j){
			if(lotions[j].spfs >= cows[i].minspf && lotions[j].spfs <= cows[i].maxspf && lotions[j].cover && lotions[j].spfs > maxlotion_spfs){
				maxlotion_spfs = lotions[j].spfs;
				maxpos = j;
			}
		}
		if(maxpos != -1){
			++ret;
			--lotions[maxpos].cover;
		}
	}
	
	printf("%d\n", ret);
	return 0;
}