HDU 4791 Alice's Print Service
从后往前预处理打印纸的最小花费。然后在询问时通过upper_bound找到位置p，比较当前打印纸张花费与相邻临界点最小花费即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
int T;
const int maxn = 100010;
const int INF = 0x3f3f3f3f;
typedef long long LL;
LL x[maxn], y[maxn];
LL cost[maxn];
int main()
{
int T;
for(scanf("%d", &T); T > 0; T--)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%I64d%I64d", &x[i], &y[i]);
cost[i] = x[i]*y[i];
}
LL pre = cost[n-1];
for(int i = n-1; i >= 0; i--)
{
if(pre < cost[i])
{
cost[i] = pre;
pre = cost[i];
}
}
while(m--)
{
LL q; scanf("%I64d", &q);
if(q >= x[n-1]) { printf("%I64d\n", q*y[n-1]); continue ; }
LL p = upper_bound(x, x+n, q)-x;
LL ans = q*y[p-1];
ans = min(ans, cost[p]);
printf("%I64d\n", ans);
}
}
return 0;
}
2014 ACM/ICPC Asia Regional 广州网赛 | HDU 5023 & HDU 5024 & HDU 5025
HDU 5203：给定一段区间，初始颜色为2，你可以将一整段区间涂成某一种颜色，询问一段区间上的颜色数。
线段树操作。由于颜色最多只有30种，我们可以利用一个int来处理所有的颜色，向下用&运算，向上用|运算来合并所有颜色即可。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000100;
#define lc o<<1
#define rc o<<1|1
struct SegmentTree
{
int color[maxn<<2];
int setv[maxn<<2];
int n;
void init(int n)
{
this->n = n;
}
void pushup(int o)
{
color[o] = color[lc] | color[rc];
}
void build(int o, int L, int R)
{
color[o] = (1<<1); setv[o] = 2;
if(L == R) return ;
int M = L+(R-L)/2;
build(lc, L, M);
build(rc, M+1, R);
pushup(o);
}
void pushdown(int o, int L, int R)
{
if(setv[o])
{
color[lc] = (1<<(setv[o]-1));
color[rc] = (1<<(setv[o]-1));
setv[lc] = setv[rc] = setv[o];
setv[o] = 0;
}
}
void update(int o, int L, int R, int y1, int y2, int v)
{
if(y1 <= L && y2 >= R)
{
color[o] = (1<<(v-1));
setv[o] = v;
return ;
}
int M = L+(R-L)/2;
pushdown(o, L, R);
if(y1 <= M) update(lc, L, M, y1, y2, v);
if(y2 > M) update(rc, M+1, R, y1, y2, v);
pushup(o);
}
int query(int o, int L, int R, int y1, int y2)
{
if(y1 <= L && y2 >= R) return color[o];
int M = L+(R-L)/2;
pushdown(o, L, R);
int ans = 0;
if(y1 <= M) ans |= query(lc, L, M, y1 ,y2);
if(y2 > M) ans |= query(rc, M+1, R, y1, y2);
return ans;
}
void print(int o, int L, int R)
{
printf("%d ", color[o]);
if(L == R) return ;
int M = L+(R-L)/2;
print(lc, L, M); print(rc, M+1, R);
}
};
////////////////
void readint(int &x)
{
char c = getchar();
while(!isdigit(c)) c = getchar();
x = 0;
while(isdigit(c))
{
x = x*10+c-'0';
c = getchar();
}
}
void writeint(int x)
{
if(x > 9) writeint(x/10);
printf("%d", x%10);
}
SegmentTree g;
int n, m, c;
int main()
{
while(~scanf("%d%d", &n, &m))
{
if(n == 0 && m == 0) break;
g.init(n+10);
g.build(1, 1, n);
while(m--)
{
char cmd[10]; int x, y, z;
scanf("%s", cmd);
if(cmd[0] == 'P')
{
readint(x), readint(y), readint(z);
if(x > y)
swap(x, y);
g.update(1, 1, n, x, y, z);
}
else if(cmd[0] == 'Q')
{
readint(x), readint(y);
if(x > y)
swap(x, y);
int tmp = g.query(1, 1, n, x, y);
int ans = 1;
while(tmp)
{
if(tmp & 1 && tmp/2 != 0) writeint(ans), putchar(' ');
else if(tmp & 1) writeint(ans), puts("");
tmp >>= 1;
ans++;
}
}
}
}
return 0;
}
HDU 5204：给定一个迷宫，求最长的一条路径，该路径上任意一点都可以通过最多不超过一次的转弯到达。
[HNOI2004]宠物收养所
Splay求前驱与后继，然后累加和即可。
书上的Splay求x的前驱与后继需要插入x之后才能求得前驱与后继。删除操作时把x与前驱或者后继删除即可。
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
typedef int Comparable;
struct Node
{
Node *left, *right;
int element;
Node(int v=0, Node *lt=0, Node *rt=0):element(v),left(lt),right(rt) {}
};
Node *null = new Node();
void rotateWithLeftChild(Node *&t)
{
Node *k = t->left;
t->left = k->right;
k->right = t;
t = k;
}
void rotateWithRightChild(Node *&t)
{
Node *k = t->right;
t->right = k->left;
k->left = t;
t = k;
}
void splay(Node *&t, const Comparable &x)
{
Node *leftTreeMax, *rightTreeMin;
static Node head;
head.left = head.right = null;
leftTreeMax = rightTreeMin = &head;
null->element = x;
for(;;)
{
if(x < t->element)
{
if(x < t->left->element)
rotateWithLeftChild(t);
if(t->left == null) break;
//Link Right
rightTreeMin->left = t;
rightTreeMin = t;
t = t->left;
}
else if(x > t->element)
{
if(x > t->right->element)
rotateWithRightChild(t);
if(t->right == null) break;
//Link left
leftTreeMax->right = t;
leftTreeMax = t;
t = t->right;
}
else break;
}
leftTreeMax->right = t->left;
rightTreeMin->left = t->right;
t->left = head.right;
t->right = head.left;
}
int insert(Node *&root, const Comparable &x)
{
Node* newNode = new Node(x);
if(root == null)
{
newNode->left = newNode->right = null;
root = newNode;
return 0;
}
splay(root, x);
if(x < root->element)
{
newNode->left = root->left;
newNode->right = root;
root->left = null;
root = newNode;
}
else if(x > root->element)
{
newNode->right = root->right;
newNode->left = root;
root->right = null;
root = newNode;
}
else return -1;
newNode = NULL;
return 1;
}
void printTree(Node *o)
{
if(o != null)
{
printf("%d ", o->element);
printTree(o->left);
printTree(o->right);
}
}
void remove(Node *&o, int x)
{
splay(o, x);
if(o->element != x) return ;
Node *newTree;
if(o->left == null)
newTree = o->right;
else
{
newTree = o->left;
splay(newTree, x);
newTree->right = o->right;
}
delete o;
o = newTree;
}
Node *findMin(Node *o)
{
if(o == null) return null;
while(o->left != null)
o = o->left;
return o;
}
Node *findMax(Node *o)
{
if(o == null) return null;
while(o->right != null)
o = o->right;
return o;
}
Node *predecessor(Node *o, int x)
{
splay(o, x);
return findMax(o->left);
}
Node *successor(Node *o, int x)
{
return findMin(o->right);
}
///////////////////////
int n;
const int INF = 0x3f3f3f3f;
void readint(int &x)
{
char c = getchar();
while(!isdigit(c)) c = getchar();
x = 0;
while(isdigit(c))
{
x = x*10+c-'0';
c = getchar();
}
}
int main()
{
while(~scanf("%d", &n))
{
Node *root = null; root->left = null; root->right = null;
int ans = 0, flag = -1;
for(int i = 1; i <= n; i++)
{
int cmd, x; scanf("%d%d", &cmd, &x);
if(flag == -1)
{
insert(root, x);
flag = cmd;
}
else if(flag == cmd)
{
insert(root, x);
}
else
{
int p = insert(root, x);
if(p == -1)
{
remove(root, x);
}
else
{
Node *pre = predecessor(root, x);
Node *next = successor(root, x);
int t1 = pre != null? pre->element:INF;
int t2 = next != null? next->element:INF;
if(abs(t1-x) <= abs(t2-x))
{
ans = (ans+abs(t1-x))%1000000;
remove(root, t1);
remove(root, x);
}
else
{
ans = (ans+abs(t2-x))%1000000;
remove(root, t2);
remove(root, x);
}
}
if(root == null) flag = -1;
}
}
printf("%d\n", ans%1000000);
}
return 0;
}
Splay伸展树
Splay伸展树
Splay是二叉查找树，不是一颗平衡树，但可以通过自调整达到一种近似平衡的情况。Splay在连续M次操作中均摊时间复杂度是M*logn，其中n为节点的个数，M为操作的次数。Splay的操作与特点将在以下介绍。
- 当访问一个节点时，立即把当前访问的节点旋转到根节点，让访问（插入）的节点立马成为新的根节点。
- 旋转操作与AVL很像，有两种旋转，左旋、右旋。
- Splay操作有两种不同的实现方式。一种是自底向上的旋转，需要记录当前节点的父亲节点。另外一种是自顶向上的实现方式，不需要记录父亲节点。
- 由于Splay把当前访问的节点放在根节点，很容易求出当前节点的前驱与后继。
- Splay支持merge、split、findMin、findMax、predecessor、successor、insert、remove等操作。
- 在信息学竞赛中，Splay可以实现能实现线段树的所有的功能，即pushup、pushdown维护区间信息在Splay中用的很活，但Splay又支持快速的序列分离和合并，这是线段树做不到的。
- 验证自己手写的数据结构是否正确可以去OJ写一写用到该数据结构的题。
Treap树
最近在学高级数据结构，AVL、BST、SPLAY、Treap、红黑树等，能够快速实现AVL、BST、SPLAY、Treap，以及会利用简单变形解决某些问题就达到要求了。
大学计算机专业的学生，数据结构书上的所有数据结构能够快速实现，对计算机理论不至于精通，但要熟悉，随便提出一个基础理论至少不陌生。高数、现代、概率论都要达到熟悉的地步。
Treap,顾名思义，Tree+Heap的简称，与BST不同，节点还附加了一个随机优先级来平衡树，所以又带有堆的性质，可以证明最坏的查找、删除效率为O(logn)，它可以做到set做不到的事，如快速求第K大值，以及求值x的名次，也被称作名次树。如果附加的优先级是固定的话，那么就成了笛卡尔树。
HDU 4970 Killing Monsters
比赛时线段树超时，然后用树状数组暴力过了。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
typedef long long LL;
void readint(LL &x)
{
char c = getchar();
while(!isdigit(c)) c = getchar();
x = 0;
while(isdigit(c))
{
x = x*10+c-'0';
c = getchar();
}
}
void writeint(LL x)
{
if(x > 9) writeint(x/10);
putchar(x%10+'0');
}
/////////////////////////////////
const LL maxn = 100000 + 10;
LL n, m;
LL C[maxn];
LL lowbit(LL x)
{
return x & -x;
}
void add(LL x, LL d)
{
while(x > 0)
{
C[x] += d; x -= lowbit(x);
}
}
LL sum(LL x)
{
LL ans = 0;
while(x <= n)
{
ans += C[x]; x += lowbit(x);
}
return ans;
}
LL f[maxn];
int main()
{
for(;;)
{
readint(n);
if(!n) break;
for(int i = 0; i <= n; i++)
C[i] = f[i] = 0;
readint(m);
for(int i = 1; i <= m; i++)
{
LL x, y, z; readint(x), readint(y), readint(z);
add(y, z), add(x-1, -z);
}
f[n] = sum(n);
for(int i = n-1; i >= 1; i--)
{
f[i] = sum(i)+f[i+1];
}
LL k; readint(k);
LL ans = 0;
for(int i = 1; i <= k; i++)
{
LL h, x; readint(h), readint(x);
if(h > f[x]) ans++;
}
writeint(ans), puts("");
}
return 0;
}
HDU 4950 Monster & HDU 4952 Number Transformation
多校第八场，做比赛还是不够稳呐！(=@__@=)！
4950：给定一个怪物，初始HP为h，战士攻击力为a，每次回合结束后怪物能回复b的血量，如果怪物的血量<1时，判负。战士经过K轮战斗必须休息一轮，问是否能杀死怪物。
贪心即可，首先判断一次杀死的情况，在判断a<=b，永远杀不死的情况，然后再在a>b的情况里分类判断，注意int越界。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long LL;
LL h, a, b, k;
int main()
{
int kase = 0;
while(~scanf("%I64d%I64d%I64d%I64d", &h, &a, &b, &k))
{
if(h == 0 && a == 0 && b == 0 && k == 0) break;
printf("Case #%d: ", ++kase);
if(a >= h)
{
printf("YES\n");
continue ;
}
if(a <= b) printf("NO\n");
else
{
LL T = h-a*k+b*(k-1);
if(T <= 0) printf("YES\n");
else
{
LL M = h-a*k+b*(k+1);
if(M >= h) printf("NO\n");
else printf("YES\n");
}
}
}
return 0;
}
4952：打表找规律，我找到的规律大约是在sqrt(n)左右后面的项与前面的项是等差数列，而且差值=等差数列的首项x/i（i-th operation），时间复杂度大约在O(sqrt(n))，对10^10次方左右的数据足够了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long LL;
LL work(LL x, LL i)
{
if(x%i == 0) return x;
LL q = x/i*i+i;
return q;
}
LL n, k;
int main()
{
int kase = 0;
while(~scanf("%I64d%I64d", &n, &k) && (n+k))
{
LL x, y;
x = n;
LL i, a;
LL b;
for(i = 2; i <= k; i++)
{
y = x;
x = work(x, i);
a = x-y;
b = x/i;
if(x%i == 0 && a == b) break;
}
if(i <= k) x += (k-i)*b;
printf("Case #%d: %I64d\n", ++kase, x);
}
return 0;
}
HDU 4961 Magical Forest
大意：虚拟出一个2*10^9 * 2*10^9的数组内存空间，现在这个内存空间初始化为0，并且对其中的某些元素进行赋初值。后接着一系列的操作使得这个数组的行和列得以交换，中间还对某一行或者是某一列元素的值进行询问。
前段时间写过一个类似的题，二哥的内存。没想到在多校遇到了这道题，只不过数据范围改一下，但是有一个限制条件，即交换的两行（列）必须都有水果或者都没水果，注意这一点，用map映射一下值就可以了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
using namespace std;
map<long long int, int> mp;
map<int, int> r, c;
int n, m, k;
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
int main()
{
int T, kase = 0;
for(scanf("%d", &T); T > 0; T--)
{
scanf("%d%d%d", &n, &m, &k);
mp.clear();
r.clear();
c.clear();
for(int i = 0; i < k; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
mp[1LL*x*2000000005+y] = z;
r[x] = x, c[y] = y;
}
int q; scanf("%d", &q);
printf("Case #%d:\n", ++kase);
while(q--)
{
int cmd, x, y;
scanf("%d%d%d", &cmd, &x, &y);
if(cmd == 1)
{
if(r.count(x) && r.count(y))
{
swap(r[x], r[y]);
}
if(!r.count(x) && !r.count(y))
{
r[x] = x, r[y] = y;
swap(r[x], r[y]);
}
}
else if(cmd == 2)
{
if(c.count(x) && c.count(y))
{
swap(c[x], c[y]);
}
if((!c.count(x) && !c.count(y)))
{
c[x] = x, c[y] = y;
swap(c[x], c[y]);
}
}
else
{
if(mp[1LL*r[x]*2000000005+c[y]] != 0)
{
printf("%d\n", mp[1LL*r[x]*2000000005+c[y]]);
}
else printf("0\n");
}
}
}
return 0;
}
HDU 4930 Fighting the Landlords
给定斗地主的规则以及两幅手牌，然后判断是否在这一轮内你不会输给对手或者出完了全部手牌。
在比赛中我判断所有的情况，这样比较麻烦。其实可以把Bomb、Tri、Pair拆开分别去判断，有很多细节需要注意。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int x[20], y[20];
int Win(int n)
{
if(n == 4 || n == 6) //炸弹带
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 4) return 1;
}
}
if(n == 5) //3带2
{
int Tri = 0, Dou = 0;
for(int i = 17; i >= 3; i--)
{
if(x[i] == 3) Tri = 1;
if(x[i] == 2) Dou = 1;
}
if(Tri && Dou) return 1;
}
if(n == 4) //3带1
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 3) return 1;
}
}
if(n == 3) //三个
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 3) return 1;
}
}
if(n == 2) //Double
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 2) return 1;
}
}
if(n == 1) return 1; //一个
return 0;
}
int main()
{
int T;
for(scanf("%d", &T); T > 0; T--)
{
char s[20];
scanf("%s", s);
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
for(int i = 0; s[i]; i++)
{
int t;
if(s[i] == 'T') t = 10;
else if(s[i] == 'J') t = 11;
else if(s[i] == 'Q') t = 12;
else if(s[i] == 'K') t = 13;
else if(s[i] == 'A') t = 14;
else if(s[i] == '2') t = 15;
else if(s[i] == 'X') t = 16;
else if(s[i] == 'Y') t = 17;
else t = s[i]-'0';
x[t]++;
}
int len = strlen(s);
scanf("%s", s);
for(int i = 0; s[i]; i++)
{
int t;
if(s[i] == 'T') t = 10;
else if(s[i] == 'J') t = 11;
else if(s[i] == 'Q') t = 12;
else if(s[i] == 'K') t = 13;
else if(s[i] == 'A') t = 14;
else if(s[i] == '2') t = 15;
else if(s[i] == 'X') t = 16;
else if(s[i] == 'Y') t = 17;
else t = s[i]-'0';
y[t]++;
}
if(x[16] == 1 && x[17] == 1) //有大小王
{
printf("Yes\n");
continue;
}
if(Win(len)) { printf("Yes\n"); continue ; } //出完的情况
if(y[16] == 1 && y[17] == 1) //有大小王
{
printf("No\n");
continue;
}
int bomb = -1, p;
for(int i = 17; i >= 3; i--) //炸弹
{
if(x[i] == 4)
{
bomb = 1;
p = i;
break;
}
}
int win = 1;
if(bomb == 1)
{
for(int i = 17; i > p; i--)
{
if(y[i] == 4)
{
win = 0; break;
}
}
}
if(bomb == 1 && win) { printf("Yes\n"); continue; } //有炸弹且最大
else if(!win) { printf("No\n"); continue ;} //有炸弹，但输了。
for(int i = 3; i <= 17; i++) if(y[i] == 4) { bomb = 2; break; }
if(bomb == 2) { printf("No\n"); continue ; } //对手有炸弹，我没有。
win = 1;
int Tri = -1;
for(int i = 17; i >= 3; i--) //三个
{
if(x[i] == 3)
{
Tri = 1;
p = i;
break;
}
}
if(Tri == 1)
{
for(int i = 17; i > p; i--)
{
if(y[i] == 3)
{
Tri = 0;
break;
}
}
}
if(Tri == 1) { printf("Yes\n"); continue ;}
else if(Tri == 0) win = 0;
int Dou = -1;
for(int i = 17; i >= 3; i--) //两个
{
if(x[i] == 2)
{
Dou = 1;
p = i;
break;
}
}
if(Dou == 1)
{
for(int i = 17; i > p; i--)
{
if(y[i] == 2 || y[i] == 3)
{
Dou = 0;
break;
}
}
}
if(Dou == 1) { printf("Yes\n"); continue ; }
else if(Dou == 0) win = 0;
int solo = -1;
for(int i = 17; i >= 3; i--) //一个
{
if(x[i] == 1)
{
solo = 1;
p = i;
break;
}
}
if(solo == 1)
{
if(win == 0) win = 1;
for(int i = 17; i > p; i--)
{
if(y[i] == 1 || y[i] == 2 || y[i] == 3) { win = 0; break; }
}
}
if(win == 1) printf("Yes\n");
else if(win == 0) printf("No\n");
}
return 0;
}
Booklist
大学只剩一年了，以前看书没有计划，现在是时候整理一下以前的看过的书籍，做做阅读计划了。顺便把正在阅读的书以及准备阅读的书籍在书单中列出来。不定期更新。
2013年已阅读完：
- 1、自然科学：
- ①（物理）科普类：
- 《从一到无穷大》 （美）G.伽莫夫
- 《时间简史》 霍金
- 《平行宇宙》 加来道雄
- ②科幻小说：
- 《三体1》 地球往事 刘慈欣
- 《三体2》黑暗森林 刘慈欣
- 《三体3》 死神永生 刘慈欣
- 《白垩纪往事》刘慈欣
- 《球形闪电》刘慈欣
- 《乡村教师》 刘慈欣
- 《何夕自选科幻集》何夕
HDU 4861 Couple doubi
前天刚到学校，很久没刷题，需要一段时间寻找状态。
这是22号的多校，我没赶上，现在重新写一下来帮助自己找回状态。
由于p一定是素数，打表可知循环节为p-1，并且只有p-1号球有价值。一开始题意理解错，以为必须从第一号球开始轮流拿，其实是任意顺序拿的。这样，求出总共可以拿到几次有价值的球k，如果k为奇数则代表doubiNan可以多拿一次，输出"YES"，如果为偶数，那么他们拿的次数相等，输出"NO"。
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
int k, p;
int main()
{
while(~scanf("%d%d", &k, &p))
{
int n = k/(p-1);
if(n & 1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
用自定义类模板实现的二叉堆
最近在复习数据结构，从各种数据结构的发明不得感叹人类真的很聪明，创造了各种方式来组织数据，使得人们可以快速的获得某一想要的数据。
二叉堆具有的堆序性质就是如此。
#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
using namespace std;
#define readint(T) scanf("%d", &T)
const int INF = 0x3f3f3f3f;
template<typename Comparable>
class BHeap
{
private:
int currentSize;
vector<Comparable> array;
void buildHeap();
void percolateDown(int hole);
public:
explicit BHeap(int capacity = 100);
explicit BHeap(const vector<Comparable> &items);
bool isEmpty() const;
Comparable findMin() const;
void decreaseKey(int p, Comparable delta);
void increaseKey(int p, Comparable delta);
void insert(const Comparable &x);
Comparable deleteMin();
void makeEmpty();
void print();
};
template<typename Comparable>
void BHeap<Comparable>::insert(const Comparable &x)
{
if(currentSize == array.size() -1)
array.resize(array.size()*2);
int hole = ++currentSize;
for(; hole > 1 && x < array[hole/2]; hole /=2)
array[hole] = array[hole/2];
array[hole] = x;
}
template<typename Comparable>
Comparable BHeap<Comparable>::deleteMin()
{
Comparable ERROR = -1;
if(isEmpty())
{
printf("already Empty\n");
return ERROR;
}
Comparable minItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
template<typename Comparable>
void BHeap<Comparable>::percolateDown(int hole)
{
int child;
Comparable tmp = array[hole];
for(; hole*2 <= currentSize; hole = child)
{
child = hole*2;
if(child != currentSize && array[child+1] < array[child])
child++;
if(array[child] < tmp)
array[hole] = array[child];
else break;
}
array[hole] = tmp;
}
template<typename Comparable>
void BHeap<Comparable>::decreaseKey(int p, Comparable delta)
{
Comparable tmp = array[p]-delta;
if(tmp > array[p])
printf("The new Key is larger than current Key!!!\n");
else
{
array[p] = tmp;
int hole;
for(hole = p; hole > 1 && array[tmp] < array[hole/2]; hole /= 2)
array[hole] = array[hole/2];
array[hole] = tmp;
}
}
template<typename Comparable>
void BHeap<Comparable>::increaseKey(int p, Comparable delta)
{
Comparable tmp = array[p]+delta;
if(tmp < array[p])
printf("The new Key is smaller than current Key!!!\n");
else
{
array[p] = tmp;
percolateDown(p);
}
}
template<typename Comparable>
BHeap<Comparable>::BHeap(const vector<Comparable> &items):array(items.size()+10), currentSize(items.size())
{
for(int i = 0; i < items.size(); i++)
array[i+1] = items[i];
buildHeap();
}
template<typename Comparable>
void BHeap<Comparable>::buildHeap() //建堆只考虑有子节点的节点
{
for(int i = currentSize/2; i > 0; i--)
percolateDown(i);
}
template<typename Comparable>
bool BHeap<Comparable>::isEmpty() const
{
if(currentSize == 0) return 1;
return 0;
}
template<typename Comparable>
void BHeap<Comparable>::makeEmpty()
{
currentSize = 0;
}
template<typename Comparable>
Comparable BHeap<Comparable>::findMin() const
{
Comparable minItem = array[1];
return minItem;
}
template<typename Comparable>
void BHeap<Comparable>::print()
{
for(int i = 1; i <= currentSize; i++) printf(i != currentSize?"%d ":"%d\n", array[i]);
}
int main()
{
////////////////////////////test
vector<int> ar;
int minItem, x;
for(int i = 0; i < 10; i++)
{
readint(x);
ar.push_back(x);
}
BHeap<int> Heap(ar);
printf("findMin: %d\n", Heap.findMin());
Heap.print();
printf("Please input a digit:\n");
readint(x);
printf("after insert a digit\n");
Heap.insert(x);
Heap.print();
printf("position 1 increase 10 and percolateDown\n");
Heap.increaseKey(1, 10);
Heap.print();
printf("position 1 decrease 15 and percolateUp\n");
Heap.decreaseKey(1, 15);
Heap.print();
printf("deleteMin:\n");
Heap.deleteMin();
Heap.print();
system("pause");
}