哈夫曼思想，优先队列解决

手打版

就把上一篇堆的代码做了点改动

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

/*
poj  3253
368K	47MS
*/

#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

#define MAXN 30005
#define MAX_INT 2147483647
#define FA(x) (x>>1) 
#define LC(x) ((x<<1))
#define RC(x) ((x<<1)|1)
#define MID(x,y) ( (x + y) >> 1 )
#define TIME_BEGIN double t1 = clock()
#define TIME_END double t2 = clock();printf("\n%.2lfms\n",t2-t1)

using namespace std;

int size,top = 1;
__int64 heap[MAXN];

bool cmp(__int64 a,__int64 b)
{
	return a < b;
}

void up(int id)
{
	if(id == 1)
		return ;
	if(!cmp(heap[FA(id)] , heap[id]))
	{
		swap(heap[FA(id)] , heap[id]);
		up(FA(id));
	}
}

void down(int id)
{
	if(RC(id) <= size)
	{
		if(cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
		else if(!cmp(heap[LC(id)] , heap[RC(id)]) && cmp(heap[RC(id)] , heap[id]))
		{
			swap(heap[RC(id)] , heap[id]);
			down(RC(id));
		}
	}
	else if(LC(id) <= size)
	{
		if(cmp(heap[LC(id)] , heap[id]))
		{
			swap(heap[LC(id)] , heap[id]);
			down(LC(id));
		}
	}
}

void insert(__int64 t)
{
	heap[++size] = t;
	up(size);
}

__int64 dele()
{
	__int64 tmp = heap[top];
	if(RC(top) <= size)
	{
		if(heap[LC(top)] < heap[RC(top)])
		{
			tmp += heap[LC(top)];
			heap[LC(top)] = heap[size--];
			down(LC(top));
		}
		else
		{
			tmp += heap[RC(top)];
			heap[RC(top)] = heap[size--];
			down(RC(top));
		}
		heap[top] = tmp;
		down(top);
	}
	else
	{
		size --;
		tmp += heap[LC(top)];
	}
	return tmp;
}

void print(int num)
{
	int k = 1,cnt = 0,kk = 0;
	while(num)
	{
		num -= k;
		while(kk < k)
		{
			cnt ++; kk ++;
			cout<<heap[cnt]<<" ";
		}
		kk = 0;
		cout<<endl;
		k = min(k<<1, num);
	}
}

int main()
{
	__int64 sum = 0;
	freopen("./3253.in" , "r" , stdin);
	int n;
	cin>>n;
	if(n == 1)
	{
		cout<<0<<endl;
		return 0;
	}
	while(n--)
	{
		int t;
		scanf("%d",&t);
		insert(t);
	}
	while(size > 1)
	{
		sum+= dele();
	}
	cout<<sum<<endl;
	return 0;
}

STL偷懒版

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

/*
poj 3253
324K	32MS
*/
#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int>myQueue;
int main()
{
	int n,t;
	__int64 ans = 0;
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d",&t);t = -t;
		myQueue.push(t);
	}
	while(myQueue.size() > 1)
	{
		__int64 t1 = myQueue.top();
		myQueue.pop();
		__int64 t2 = myQueue.top();
		myQueue.pop();t1 += t2;ans += t1;
		myQueue.push(t1);
	}
	printf("%I64d\n",-ans);
	return 0;
}

题目大意：

一个人要去钓鱼，可用时间为h（小时），可选湖泊为n个，可以将湖泊看成在一条直线上的顺序的n个点，要去第k个点必须从第k-1个点出发，所用时间为t[k-1]（个5分钟），每个湖初始鱼的数目为f[i]（注意，可能为0），每个湖泊单位时间（五分钟）鱼的数目减少d[i]条（这是人在该湖泊钓鱼的情况下，人不在就不会减少）,问h时间内他能钓的鱼最多是多少？

题目分析：

贪心策略，先找到他能到达的最远的（所有时间用来跑路的极限值）湖泊p，然后分为若干种情况:他的活动范围是 11 、 12 、 ······· 1p，即他可以选择的跑去钓鱼的最远的湖泊有p个，枚举每种情况，把总时间减去跑路的时间就是他能钓鱼的时间，在情况 1k 时，对于每一个单位时间（五分钟），都从1到k枚举每个湖泊找到最大值记录相应位置，然后每种情况都算一次，迭代出最大值就可以了。

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

/*
poj  1042
236K	47MS
*/

#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 30

using namespace std;

int f[MAXN],d[MAXN],t[MAXN],n,ans[MAXN],tot[MAXN][200],h;
//tot[i][j]是第i个在湖第j个5分钟能抓的鱼的数目 

void init()
{
	h *= 12;
	for(int i = 1;i <= n;i ++)
		scanf("%d",&f[i]);
	for(int i = 1;i <= n;i ++)
		scanf("%d",&d[i]);
	for(int i = 1;i < n;i ++)
		scanf("%d",&t[i]);
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= h;j ++)
			tot[i][j] = max(f[i] - d[i] * (j - 1) , 0);
}

void calc()
{
	int far = 1,tmp[MAXN] = {0},index[MAXN] = {0},sum = -0xfffffff;//可能有全为零的情况 
	//far为其能到达并钓一会鱼的最远的湖,tmp[i]是从i出发到达下一个湖时用的跑路总时间 
	//index[i]是指为钓到最多的鱼在第i个湖待的时间 
	while(far <= n)//计算所能到达的最远的湖 
	{
		tmp[far] = tmp[far-1] + t[far];
		if(tmp[far] >= h)
			break;
		far++;
	}
	if(far > n)
		far = n;
	int cnt = 1;
	while(cnt <= far)//从近到远试遍所有情况 
	{
		int tsum = 0;
		memset(index , 0 , sizeof(index));
		int th = h - tmp[cnt-1];//可用钓鱼时间
		for(int i = 1;i <= th;i ++)//对于每一个单位时间（五分钟）都寻找最多鱼的湖 
		{
			int tmax = 0,tj = 1;//默认为第一个湖 
			for(int j = 1;j <= cnt;j ++)//最远到第cnt个湖  cnt∈[1,far] 
			{
				if(tot[j][index[j]+1] > tmax)
				{
					tj = j;//记录位置 
					tmax = tot[j][index[j]+1];//记录数目 
				}
			}
			tsum += tmax;
			index[tj] ++;//在第tj个湖已经待的时间+1 
		}
		if(tsum > sum)//替换 
		{
			sum = tsum;
			memcpy(ans , index , sizeof(index));
		}
		cnt ++;//范围扩大一个湖 
	}
	for(int i = 1;i <= n;i ++)
	{
		if(i == n)
			printf("%d\n",ans[i] * 5);
		else
			printf("%d, ",ans[i] * 5);
	}
	printf("Number of fish expected: %d\n\n",sum);
}

int main()
{
	freopen("./1042.in" , "r" , stdin);
	while(cin>>n>>h)
	{
		init();
		calc();
	}
	return 0;
}

所谓单调队列，就是支持从队尾插入删除，队头查询的一种数据结构，虽然用途不是很广泛，但是对于某些问题如：在一个被不断刷新的缓存区中多次查询最小值（最大值）非常高效

构造方法：对于单调上升队列：每次从队尾入队一个元素，都从队尾起依次删除比当前元素大的元素，强制使队列单调

示例，POJ 2823 Sliding Window

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

/*
poj  2823
8012K	5344MS
*/ 

#include<cstdio>
#include<iostream>

#define MAXN 1000005
#define MAX_INT 2147483647

using namespace std;

int que_min[MAXN][2],que_max[MAXN][2],ans_min[MAXN],ans_max[MAXN];
//que二维数组，[][0]表示元素，[][1]表示元素在输入序列中的下标 
int main()
{
	//freopen("./2823.in" , "r" , stdin);
	int m,n,h_max = 0,t_max = 0,h_min = 0,t_min = 0,t;
	/*
	h_min   t_min
	h_max   t_max
	分别是两个单调队列的头尾指针 
	*/
	que_min[0][0] = -MAX_INT; que_max[0][0] = MAX_INT;
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d",&t);
		while(t <= que_min[t_min][0] && t_min >= h_min)
		//从尾端开始，删除所有比当前元素大的元素 
		{
			t_min --;
		}
		t_min ++;
		que_min[t_min][0] = t;
		que_min[t_min][1] = i;
		while(que_min[h_min][1] <= i - m)
		//从当前位置i开始，取最小值的范围只能是[i - m + 1 , i] 
		//删除不合法的元素
		{
			h_min ++;
		}
		ans_min[i] = que_min[h_min][0];
	
		//同理计算最大值 
		while(t >= que_max[t_max][0] && t_max >= h_max)
		//从尾端开始，删除所有比当前元素小的元素 
		{
			t_max --;
		}
		t_max ++;
		que_max[t_max][0] = t;
		que_max[t_max][1] = i;
		while(que_max[h_max][1] <= i - m)
		//从当前位置i开始，取最大值的范围只能是[i - m + 1 , i]
		//删除不合法的元素
		{
			h_max ++;
		}
		ans_max[i] = que_max[h_max][0];
	}
	
	for(int i = m;i <= n;i ++)
		printf("%d ",ans_min[i]);
	printf("\n");
	for(int i = m;i <= n;i ++)
		printf("%d ",ans_max[i]);
	printf("\n");
	return 0;
}

大水题

1000. a加b 不解释
1001. 求高精度幂 高精度幂，巨多细节
1002. Hangover 套公式
1003. I Think I Need a Houseboat 虽然简单，但是做了无数次总是不能1A
1004. DNA Sorting 快排就行
1005. Packets 细节细节
1006. 高精度 细心一点就好
1007. IMMEDIATE DECODABILITY 本应该用字典树的，但是数据量只有10，就算了
1008. Cable master 精度卡哭了
1009. The Clocks 想清楚，暴力就行
1010. THE DRUNK JAILER
1011. Self Numbers 记着不难
1012. Cabric Number Problem 数字黑洞问题
1013. Bode Plot 阅读理解
1014. TEX Quotes 大水
1015. Integer Inquiry 高精度加法
1016. u Calculate e 很麻烦
1017. Digital Roots
1018. Adding Reversed Numbers 不难
1019. Clay Bully
1020. Doubles
1021. Skew数 水~
1022. Just the Facts 会写循环就行了
1023. Eva’s Problem
1024. Sorting by Swapping
1025. Yeehaa! 水！
1026. Diplomatic License
1027. Litmus Test 化学题
1028. No Brainer 题目就是最好的评价
1029. Calendar 很恶心
1030. Recaman’s Sequence 咬牙把数组开大点就行了
1031. Honey and Milk Land 理解题解+细节
1032. IP Address 水~
1033. Speed Limit 大水题
1034. Vertical Histogram 注意格式就行了
1035. ISBN 细节
1036. Specialized Four-Digit Numbers
1037. The King
1038. Lotto 简单求组合数
1039. Ones
1040. Error Correction 就是因为忘记归零参数WA了
1041. Goldbach’s Conjecture 策略选择需要稍微想一下
1042. Beat the Spread! 英语题
1043. Questions and answers 就一个快排
1044. Who’s in the Middle sort，没了
1045. Bull Math 高精度乘法
1046. Hardwood Species 快排
1047. Peter’s smokes 就当做阅读理解了
1048. How much did the businessman lose 就当做阅读理解了
1049. Very Simple Problem 记着是好像不难
1050. WERTYU 就是打表麻烦
1051. Jolly Jumpers
1052. Keep on Truckin’ 水！
1053. Series Determination 算一下公式
1054. Soundex
1055. Electrical Outlets == a+b
1056. Unhappy Jinjin 10秒AC不了就别活了，真的不夸张。10秒，至于为什么，看题就知道
1057. Trees 马路上的树
1058. Sum of Consecutive Prime Numbers 不痛不痒
1059. Big Clock 大水
1060. Pascal Library 看懂题就好
1061. A Simple Question of Chemistry 叙述的可真够麻烦的，就当练英语吧
1062. Goldbach’s Conjecture 打个素数表+细节
1063. Dirichlet’s Theorem on Arithmetic Progressions
1064. Nasty Hacks 水·~
1065. Rounders 细节@
1066. Triangular Sums 水~
1067. Quicksum
1068. Root of the Problem 细节细节+神奇的double+想清楚策略
1069. World Cup 想清楚关系就很简单了！
1070. Parkside’s Triangle
1071. Lab杯
1072. Judging Olympia
1073. Prime Gap 素数问题
1074. Beer Refrigerator 暴搜就行了
1075. Number-guessing Game
1076. The Seven Percent Solution
1077. Cow Multiplication 水~！
1078. 时间日期格式转换 大水！
1079. 分数加减法 比较麻烦
1080. 取模运算 真是。。。。
1081. 序列 高精度加法+迭代
1082. 快算24 样例就是全部的测试数据

BFS

1426. Find The Multiple 也可以用数学证明和DFS，而且都比BFS快！
1427. Knight Moves 第一道BFS
1428. Knight Moves 裸BFS
1429. Dungeon Master

DFS

1011. 木棒 经典深搜 + 酷炫剪枝
1012. 滑雪 记忆化搜索
1013. 生日蛋糕 剪枝很重要
1014. The 3n + 1 problem
1015. 棋盘问题
1016. Find The Multiple 也可以用数学证明和BFS
1017. Oil Deposit 经典深搜
1018. Function Run Fun 记忆化搜索
1019. 放苹果 勉强算是吧
1020. Red and Black 稍微有点弯的深搜
1021. Zipper 深搜
1022. Lake Counting 经典深搜
1023. A Knight’s Journey 简单DFS
1024. Sudoku 数独问题
1025. 迷宫问题

DP

1014. Dividing想清楚一个点后多重背包就可以了
1015. 需要先稍微想一下~之后很简答
1016. Human Gene Functions LCS变形，注意边界处理
1017. Brackets Sequence 确实需要好好想想
1018. LITTLE SHOP OF FLOWERS 分析关系
1019. The Triangle 数字三角形
1020. Cash Machine 多重背包
1021. Common Subsequence 最长公共子序列
1022. Coins 多重背包
1023. Divisibility 很帅的递推
1024. Charlie’s Change记录路径的多重背包 很吊
1025. Testing the CATCHER 最长不上升子序列
1026. Chores 想清楚关系再递推
1027. World Cup Noise 斐波那契 数列
1028. Alphacode 细节 递推
1029. Jumping Cows 想清楚 核心代码很简单
1030. Apple Catching 想清楚挺水的
1031. Space Elevator 多重背包
1032. Longest Ordered Subsequence 最长上升/下降 子序列
1033. Cow Bowling 数字三角形
1034. Charm Bracelet 0-1背包

计算机几何

2365. Rope 傻瓜凸包

STL 水过

1028. Web Navigation 算是用到了栈，STL水过
1029. Anagram next_permutation 水过
1030. Orders next_permutution 水过
1031. 排列 next_permutation 水过
1032. Stripies 优先级队列
1033. Babelfish map 可水 字典树王道

模拟

1006. 生理周期 简单模拟
1007. Financial Management 。。。
1008. 玛雅历 细节细节
1009. Color Me Less
1010. Parencodings
1011. Moving Tables
1012. Safecracker 略麻烦
1013. Box of Bricks 模板里总结了这类移动问题
1014. Machined Surfaces 看懂题目就好
1015. Perfect Cubes 暴搜即可
1016. Eva’s Problem 不难
1017. Distance on Chessboard 简单找规律
1018. Gold Coins
1019. Cornfields
1020. When Can We Meet? 模拟
1021. Filling Out the Team 不难
1022. Above Average 不难
1023. Blocks 不难
1024. Bank Interest 水~
1025. Feed Accounting 模拟喂牛 细心：
1026. Blurred Vision 应该不难吧
1027. Prerequisites? 应该不难
1028. Monthly Expense 二分法
1029. ICPC Score Totalizer Software 大水题
1030. Ecology tax 题目混乱做的也混乱
1031. Look and Say

数据结构

1028. Web Navigation 算是用到了栈，STL水过
1029. Mobile phones 二维树状数组（最佳） . 线段树，很重要！
1030. Crazy Search 第一道hash
1031. Jungle Roads 最小生成树模板
1032. Agri-Net 最小生成树模板
1033. The Perfect Stall 二分图最大匹配问题
1034. Rails 算是对单栈排序输出序列的理解吧，想清楚细节
1035. Find them, Catch them 种类并查集
1036. Truck History 最小生成树模板
1037. Stripies 大顶堆
1038. 食物链 种类并查集
1039. K-th Number 划分树原型，很重要！
1040. Ultra-QuickSort 归并排序，点树，树状数组
1041. BST 二叉排序树的的外壳，位运算的本质
1042. Stars 树状数组
1043. Constructing Roads 稍微变动的最小生成树
1044. Highways 最小生成树模板
1045. Babelfish 字典树 ，map可水
1046. Ubiquitous Religions 简单并查集
1047. Mayor’s posters 熟悉掌握线段树以及离散的好题！
1048. Sliding Window 单调队列，RMQ，线段树
1049. Fence Repair 优先队列
1050. A Simple Problem with Integers 树状数组（真漂亮）. 线段树
1051. Building Roads 稍微变动的最小生成树
1052. Phone List 字典树

数学证明类

1012. Joseph 约瑟夫环公式+枚举+记忆
1013. 取石子游戏 博弈论
1014. 另类数制转换 吊 Octal Fractions
1015. Ugly Numbers 理同 2591
1016. Factorial
1017. Big Number string公式或者暴力lg都可以
1018. Find The Multiple 这样略麻烦，可以用BFS DFS简单过
1019. Deck 数学公式
1020. Number Steps 其实也挺水的
1021. Sum 想到这么证的人真吊
1022. Count on Canton 简单规律
1023. The Cow Lineup 神犇牛推
1024. Power of Cryptography 神奇的double 严格证明需要泰勒展开式
1025. Herd Sums 简单公式推导
1026. Lost Cows 需要证明推导
1027. Moo Volume 公式推导很麻烦
1028. Binomial Showdown 虽然水，还是WA了很久，而且避免超时还是需要一点数学知识
1029. Set Definition 苦逼快排死得连渣都没有，大神代码果然风骚！
1030. Faulty Odometer 找数学规律，也要细心
1031. Sequence Sum Possibilities 简单数学公式
1032. Gau? in Elementary School 公式
1033. Fibonacci 斐波那契数列矩阵加速求法
1034. Ride to School 其实算不上证明，想清楚很水的

贪心策略

1042. Gone Fishing
1043. To the Max 稍微转换一下就是最大子段和
1044. Best Cow Fences 类似最大连续子段和思想,但是自己尚不能做到举一反三
1045. Tian Ji — The Horse Racing 要好好想想
1046. Maximum sum 和2593 一模一样
1047. Max Sequence

字符串

1002. 487-3279 字符串+排序
1003. Spell checker 要么笨一点加一点剪枝，要么聪明一点想清楚关系，字典树太慢了，暴力就行
1004. Tanning Salon 很简单，栈的思想
1005. 史上最难的问题（←这货只是题目） 凯撒密码
1006. Word Amalgamation
1007. Mileage Bank 不难
1008. Perfection 不难
1009. Easier Done Than Said? 不难
1010. All in All 挺水的
1011. Period 同2406 Power Strings 天才才能想到用next！！
1012. Symmetric Order 简单
1013. To and Fro 不难
1014. Message Decowding 密码
1015. Ancient Cipher 凯撒密码
1016. Guessing Game 不难，但是过得并不顺利，细节
1017. Power Strings 天才才能想到用next！！
1018. Celebrity jeopardy 最水的一道题，没有之一
1019. Surprising Strings
1020. Subsequence
1021. Oulipo 简单KMP
1022. 破译密码 又是凯撒密码
1023. 字符串替换