算法题整理——堆

发表于 | 分类于 |

POJ1456_Supermarket

描述

超市里的商品有两个属性，过期时间和利润值，现在规定过期商品只能丢掉，而且超市每天只能卖一件商品，求获利最大值。

数据范围

商品数目，过期时间和利润均为1e4之内的正整数。

思路

不妨先假设没有两件商品在同一天过期。

显然到最后一件商品过期的那天，超市只剩下了这一种商品可以卖。

那么，最好的方式就是在这一天卖掉它，因为不卖的话，这件商品要么卖不出去，要么在之前的一天卖掉。在之前的一天卖掉，就有可能抢掉另一件商品的销路。

所以不如就在最后一天卖了。

那么我们倒着考虑，最后一件商品过期的前一天呢？我们总能找到一件临过期的商品，然后卖掉。

现在，有两件商品会在同天过期了。

我们再从最后一天开始考虑，假设最后一天过期的商品有x件，显然我们会卖利润最高的。

再考虑前一天，去掉最后一天卖掉的那件，剩下x-1件和前一天过期的y件该怎么选呢？显然这时候所有的商品依然等价——因为过了这一天就是最后一天，而最后一天卖的东西已经定了，所以这天对这些商品还是最后的机会，我们还是要选其中利润最高的。

于是，我们维护一个利润优先大顶堆，逆序遍历过期时间，每天加入临过期的物品，然后取堆顶卖掉。

解决

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

using namespace std;

const int N = 1e4 + 5;

int n, len;

struct good{
	int p;
	int d;
}gds[N];

bool cmp1(good g1, good g2){
	if(g1.d == g2.d) return g1.p > g2.p;
	return g1.d > g2.d;
}

bool cmp2(good g1, good g2){
	if(g1.p == g2.p) return g1.d < g2.d;
	return g1.p > g2.p;
}

good h[N];

void Insert(good g){
	h[++len] = g;
	int fa = len >> 1;
	int cur = len;
	while(fa && cmp2(h[cur], h[fa])){
		swap(h[cur], h[fa]);
		cur = fa;
		fa >>= 1;
	}
}

good Gettop(){
	swap(h[len], h[1]);
	int cur = 1, child = 2;
	while(child < len){
		if(child != len - 1 && cmp2(h[child + 1], h[child])) ++child;
		if(cmp2(h[child], h[cur])){
			swap(h[child], h[cur]);
			cur = child;
			child *= 2;
		}else break;
	}
	return h[len--];
}

int main(){
	while(scanf("%d", &n) != EOF){
		len = 0;
		memset(h, 0, sizeof(h));
		for(int i = 0; i < n; ++i){
			scanf("%d %d", &gds[i].p, &gds[i].d);
		}
		sort(gds, gds + n, cmp1);
		int ts = gds[0].d;
		int tot = 0;
		int ans = 0;
		for(int i = ts; i; --i){
			while(gds[tot].d == i){
				Insert(gds[tot]);
				++tot;
			}
			if(len == 0) continue;
			else ans += Gettop().p;
		}
		printf("%d\n", ans);
	}
	return 0;
}

POJ2442_Sequence

描述

有m个长度为n的序列，每个序列取一个数求和，可以有m^n种取法，现在求其中最小的n种取法下的和。

思路

对于两个序列，可以在n^2种取法中找到n种最小的取法，得到新序列。

用这个新序列和第三个序列去重复上面的取法，这就是m = 3时候的解决方法。

重复m次，算法的时间复杂度是O(mn²)。

考虑优化每次操作，我们给两个序列a，b排序，显然最小的取法是a0 + b0，我们把a0 + b0到a0 + bn-1依次放进大顶堆，然后依次固定ai遍历bj，如果此时ai+bj已经大于堆顶，ai后移，如果ai+b0已经大于堆顶，结束。

时间复杂度达到O(mnlogn)。

解决

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

using namespace std;

const int M = 105;
const int N = 2005;

int t, m, n, temp;

int a[N];
int b[N];

int main(){
	scanf("%d", &t);
	while(t--){
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		
		priority_queue<int> q;
		
		scanf("%d %d", &m, &n);
		
		for(int i = 0; i < n; ++i){
			scanf("%d", &temp);
			q.push(temp);
		}
		
		if(m == 1){
			for(int j = n - 1; j >= 0; --j){
				a[j] = q.top();
				q.pop();
			}
			printf("%d", a[0]);
			for(int i = 1; i < n; ++i) printf(" %d", a[i]);
			printf("\n");
		}else{
			for(int i = 1; i < m; ++i){
				for(int j = n - 1; j >= 0; --j){
					a[j] = q.top();
					q.pop();
				}
				for(int j = 0; j < n; ++j) scanf("%d", &b[j]);
				sort(b, b + n);
				for(int j = 0; j < n; ++j) q.push(b[0] + a[j]);
				for(int j = 1; j < n; ++j){
					for(int k = 0; k < n; ++k){
						if(b[j] + a[k] < q.top()){
							q.pop();
							q.push(b[j] + a[k]);
						}else break;
					}
				}
			}
			for(int j = n - 1; j >= 0; --j){
				a[j] = q.top();
				q.pop();
			}
			printf("%d", a[0]);
			for(int i = 1; i < n; ++i) printf(" %d", a[i]);
			printf("\n");
		}
	}
	return 0;
}

BZOJ1150_数据备份

描述

你在一家 IT 公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼（或总计2K个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 2K个办公楼一定是相异的）。此外，电信公司需按网络电缆的长度（公里数）收费。因而，你需要选择这 K 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。

思路

稍加思索可以想出电缆之间是不能重叠的，否则一定有更小的方法。

又显然电缆必须选择相邻的两楼，否则可以收缩更小。

就变成了从一些线段中选不相邻的K个，使距离最小……

可惜再往后就没了思路……

本题的贪心算法是这样的：

假设就选两个线段，每次能够选择的线段有两种：

1 最短的线段S+不相邻的线段中最短的L

2 最短的线段旁边的两个

考虑其他选法：

3 非1 2的任意选法

那么3中顶多有一个和最短的线段相邻，也有可能一个也没有，那么至少有一个不和最短的线段相邻，假设它为H，那么H将大于1中不相邻的最短L，另一个一定大于最短的线段，所以3不如1。

考虑每次都选择最短的线段，即选策略1，但如果之后发现2更好想“反悔”怎么办？

这就提出了两个要求，首先我们能看得到2的好，其次我们可以反悔。

反悔之后，对结果的贡献是S两边的两个线段减去S的值，我们不妨在每次选走线段S后，把S相邻的两个线段取出，建立一个抽象的新线段，其值等于S两边的两个线段减去S的值，这样，如果它真的更好，第二次取最小值时一定会取到。

为了支持这样的操作，我们需要实现一个可以删除任意元素的堆。每次取堆顶，删除堆顶节点的相邻节点，然后压入新节点。

为了快速知道堆顶元素的相邻节点是谁已经它们在堆中的位置，我们需要一个辅助链表和辅助哈希数组。

解决

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

int n, k, len;

int a[N], nxt[N], pre[N], id[N], b[N];

pair<int, int> h[N];

void Insert(pair<int, int> x){
	h[++len] = x;
	id[x.second] = len;
	int cur = len;
	int fa = cur >> 1;
	while(fa && h[cur] < h[fa]){
		swap(h[fa], h[cur]);
		swap(id[h[fa].second], id[h[cur].second]);
		cur = fa;
		fa = cur >> 1;
	}
	/*
	for(int i = 0; i < len; ++i) printf("%d %d\n", h[i + 1].first, h[i + 1].second);
	printf("\n");
	*/
}

pair<int, int> Gettop(){
	swap(h[1], h[len]);
	swap(id[h[1].second], id[h[len].second]);
	int cur = 1, child = 2;
	while(child < len){
		if(child < len - 1 && h[child + 1] < h[child]) ++child;
		if(h[cur] > h[child]){
			swap(h[cur], h[child]);
			swap(id[h[cur].second], id[h[child].second]);
			cur = child;
			child <<= 1;
		}else break;
	}
	return h[len--];
}

void Remove(int i){
	swap(h[i], h[len]);
	swap(id[h[i].second], id[h[len].second]);
	int cur = i, child = cur << 1;
	while(child < len){
		if(child < len - 1 && h[child + 1] < h[child]) ++child;
		if(h[cur] > h[child]){
			swap(h[cur], h[child]);
			swap(id[h[cur].second], id[h[child].second]);
			cur = child;
			child <<= 1;
		}else break;
	}
	cur = i;
	int fa = cur >> 1;
	while(fa && h[cur] < h[fa]){
		swap(h[fa], h[cur]);
		swap(id[h[fa].second], id[h[cur].second]);
		cur = fa;
		fa = cur >> 1;
	}
	--len;
}

int main(){
	//freopen("in3.txt", "r", stdin);
	len = 0;
	
	scanf("%d %d", &n, &k);
	
	for(int i = 0; i < n; ++i){
		scanf("%d", &b[i]);
	}
	
	for(int i = 0; i < n - 1; ++i){
		a[i] = b[i + 1] - b[i];
	}
	
	--n;
	/*
	for(int i = 0; i < n; ++i){
		printf("%d\n", a[i]);
	}
	printf("\n");
	*/
	for(int i = 0; i < n; ++i){
		Insert(make_pair(a[i], i));
		nxt[i] = i + 1;
		pre[i] = i - 1;
	}
	/*
	for(int i = 0; i < n; ++i){
		printf("%d\n", id[i]);
	}
	printf("\n");
	*/
	int ret = 0;
	
	while(k--){
		pair<int, int> temp = Gettop();
		ret += temp.first;
		if(pre[temp.second] != -1 && nxt[temp.second] != n){
			Remove(id[pre[temp.second]]);
			Remove(id[nxt[temp.second]]);
			a[temp.second] = a[nxt[temp.second]] + a[pre[temp.second]] - a[temp.second];
			pre[temp.second] = pre[pre[temp.second]];
			nxt[temp.second] = nxt[nxt[temp.second]];
			if(pre[temp.second] != -1) nxt[pre[temp.second]] = temp.second;
			if(nxt[temp.second] != n) pre[nxt[temp.second]] = temp.second;
			temp.first = a[temp.second];
			Insert(temp);
		}else if(pre[temp.second] == -1 && nxt[temp.second] != n){
			Remove(id[nxt[temp.second]]);
			pre[nxt[nxt[temp.second]]] = -1;
		}else if(pre[temp.second] != -1 && nxt[temp.second] == n){
			Remove(id[pre[temp.second]]);
			nxt[pre[pre[temp.second]]] = n;
		}
	}
	
	printf("%d\n", ret);
}

备注

被这题困扰了很久，光是想思路就花费了一个下午，然后写链表和哈希数组完成之后一直错，到最后调试到完全找不到错误，就开始用了随机样例挑错，可找到的错误样例都是规模在300以上的，试图简化样例可哪怕改动一丢丢，我的程序和样程就会合拍，一度崩溃。

回来下了一晚上象棋之后，夜里又不甘心地翻看蓝书，发现自己的remove操作没有向上更新。

或许这就是人生吧……