ACM_JLINE.

贪心课件

贪心
字数统计: 1.9k阅读时长: 9 min
2019/03/14 Share

贪心

(当然又是备课)

Sunscreen

原题链接：POJ 3614

题目大意：

有 n 头奶牛需要 minSPF[i] 和 maxSPF[i] 单位强度的阳光。有 L 种防晒霜，每一种防晒霜有一个 SPF[i] 值，和 cover[i] 瓶。
求最多可以满足多少头奶牛。

题解：

根据奶牛的 minSPF 递减排个序就行，挺好理解。
直接上代码。

Code block

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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring> 
#define pii pair<int, int>
using namespace std;

struct node{
	int mmin, mmax;
}c[2505];

struct node1{
	int s, num;
}l[2505];

int n, m;
int x, y;

bool cmp(node a, node b){
	if(a.mmin == b.mmin) return a.mmax > b.mmax;
	return a.mmin > b.mmin;
}

bool cmp2(node1 a, node1 b){
	return a.s > b.s;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++){
		scanf("%d%d", &c[i].mmin, &c[i].mmax);
	}
	
	for(int i = 0; i < m; i++){
		scanf("%d%d", &l[i].s, &l[i].num);
	}
	
	sort(c, c + n, cmp);
	
	sort(l, l + m, cmp2);
	
	int ans = 0, tot = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(l[j].num && l[j].s >= c[i].mmin && l[j].s <= c[i].mmax){
				tot++;
				l[j].num--;
				break;
			}
		}
	}
	
	printf("%d\n", tot);
	return 0;
}

Stall Reservations

原题链接：POJ 3190

题目大意：

有 n 头牛需要在牛棚吃草，每一头牛都有一个时间段，他们不能重合(即不能在同一个牛棚有两头牛在吃草)，问至少需要提供多少个牛棚。

题解：

用个优先队列降一下复杂度就 OK 了。
直接上代码。

Code block

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 <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;

int n, use[50005];
struct node{
	int l, r;
	int id;
	bool operator < (const node &b) const{
		if(l == b.l) return r < b.r;
		return l < b.l;
	}
}a[50005];

struct Node{
	int id, time;
	bool operator < (const Node &b) const{
		return time > b.time;
	}
};

priority_queue <Node> q;

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d%d", &a[i].l, &a[i].r);
		a[i].id = i + 1;
	}
	
	sort(a, a + n);
	
	int num = 1;
	use[a[0].id] = 1;
	q.push((Node){1, a[0].r});
	
	for(int i = 1; i < n; i++){
		Node tmp = q.top(); q.pop();
		if(tmp.time >= a[i].l) {
			num++;
			q.push((Node){num, a[i].r});
			use[a[i].id] = num;
			q.push(tmp);
		}
		else{
			q.push((Node){tmp.id, a[i].r});
			use[a[i].id] = tmp.id;
		}
	}
	
	printf("%d\n", num);
	for(int i = 1; i <= n; i++){
		printf("%d\n", use[i]);
	}
	
	return 0; 
}

Radar Installation

原题链接：POJ 1328

题目大意：

二位坐标轴上有 n 个点，现在有半径为 r 的监控设备。需要把所有点在监控范围内，至少需要多少个设备。所有设备都是在 x 轴上。

题解：

有每一点转到 x 轴， 代表监控设备的范围。那么问题就变成了有 n 段区间，在每段区间内必须有一个点， 问至少需要几个点。
这个问题就是很经典的区间贪心问题了，按左端排序，设备尽量往右边靠就行。

Code block

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n, r;
int x, y;
struct Node{
	int x, y;
}b[1005];

struct node{
	double l, r;
	bool operator < (const node &b) const{
		if(l == b.l) return r < b.r;
		return l < b.l;
	}
}a[1005];

int main(){
	int Case = 1;
	while(scanf("%d%d", &n, &r) && n && r){
		int flag = 0;
		for(int i = 0; i < n; i++){
			scanf("%d%d", &b[i].x, &b[i].y);
			if(b[i].y > r) flag = 1;
		}
		
		if(flag){
			printf("Case %d: %d\n", Case++, -1);
			continue;
		}
		for(int i = 0; i < n; i++){
			a[i].l = (double)b[i].x - sqrt(r*r - b[i].y*b[i].y);
			a[i].r = (double)b[i].x + sqrt(r*r - b[i].y*b[i].y);
		}
		
//		for(int i = 0; i < n; i++){
//			printf("%.lf %.lf\n", a[i].l, a[i].r);
//		}
		
		sort(a, a + n);
		
		double pos = -1e9;
		int num = 0;
	
		for(int i = 0; i < n; i++){
			if(pos < a[i].l){
				num++;
				pos = a[i].r;
			} 
			else{
				pos = min(pos, a[i].r);
			}
		}
		
		 printf("Case %d: %d\n", Case++, num);
		
	}
	
	return 0;
}

国王游戏

原题链接：NOIP 2012

题目大意：

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

题解：

当然还是排序， 按左右手的乘积升序。
为什么要这么排序呢?

可以算一下两个大臣，然后给他们交换位置，这时候与上次比较一下，为了满足题意， 就能发现只和他们自己手上的乘积有关。推广到 n 个当然也成立了。
里面的写的很详细了传送门
注意高精度。c++写个高精度就算了，copy一份吧(emmmmmm).

Code block

1
//懒得写了

Color a Tree

原题链接：POJ 2054

题目大意：

一棵有 n (1 ≤ n ≤ 1000) 个节点的树，每个节点 i ( 1 ≤ i ≤ n) 都有一个权值
Ai。现在要把这棵树的节点全部染色，染色的规则是：根节点R可
以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。每次染
色的代价为T* A[i]，其中 T 代表当前是第几次染色。求把这棵树染色的最小总代价。

题解：

蛮有意思的，等效转换。每次染色肯定挑选最大的， 但是因为首先的父亲节点必须先染色，所有可以把这个点和它的父亲节点看成集合，然后并查集操作一下就行，注意每个点的代价。

Code block

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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 1005;
int n, r;
int c[N], fa[N], v[N], num[N], sum[N], f[N];

int Find(int x){
	return fa[x] == x ? x : fa[x] = Find(fa[x]); 
}

int main(){
	while(~scanf("%d%d", &n, &r)){
		if( n == 0 && r == 0) break;
		for(int i = 1; i <= n; i++){
			v[i] = 0;
			scanf("%d", &c[i]);
			fa[i] = i;
			num[i] = 1;
			sum[i] = c[i];
		}
		
		int x, y;
		for(int i = 1; i < n; i++){
			scanf("%d%d", &x, &y);
			f[y] = x;
		}
		
		int ans = 0;
		for(int i = 1; i < n; i++){
			double Max = 0.0;
			int p, F;
			for(int j = 1; j <= n; j++){
				F = Find(j);
				if(j != r && !v[j] && sum[F] * 1.0 / num[Find(F)] > Max){
					Max = sum[F] * 1.0 / num[Find(F)];
					p = j;
				}
			}
		//	printf("%d ", p);
			v[p] = 1;
			
			int u = Find(f[p]), v = Find(p);
			fa[v] = u;
			
			ans += sum[v] * num[u];
			sum[u] += sum[v];
			num[u] += num[v];
			
		//	printf("%d  ", ans);
		}
		ans += sum[Find(r)];
		printf("%d\n", ans);
	}
	return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/03/14/贪心/

发表日期：March 14th 2019, 9:01:36 pm

更新日期：March 14th 2019, 9:01:19 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 贪心
    1. 1.1. Sunscreen
    2. 1.2. 原题链接：POJ 3614
      1. 1.2.1. 题目大意：
      2. 1.2.2. 题解：
      3. 1.2.3. Code block
    3. 1.3. Stall Reservations
    4. 1.4. 原题链接：POJ 3190
      1. 1.4.1. 题目大意：
      2. 1.4.2. 题解：
      3. 1.4.3. Code block
    5. 1.5. Radar Installation
    6. 1.6. 原题链接：POJ 1328
      1. 1.6.1. 题目大意：
      2. 1.6.2. 题解：
      3. 1.6.3. Code block
    7. 1.7. 国王游戏
    8. 1.8. 原题链接：NOIP 2012
      1. 1.8.1. 题目大意：
      2. 1.8.2. 题解：
      3. 1.8.3. Code block
    9. 1.9. Color a Tree
    10. 1.10. 原题链接：POJ 2054
      1. 1.10.1. 题目大意：
      2. 1.10.2. 题解：
      3. 1.10.3. Code block
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路