堆是一个很强大的东西
在排序的时候 贪心时 经常用到 下面先来一道题:
Frence Repair
为了修理栅栏 要将一块很长的木板切成N块 准备切成的木板产长度为L1 L2 L3...Ln 未切割木板前的长度恰好为切割后的木板长度的总和 EG： 长度为21的木板 要最终切成5 8 8 的三块木板 在切割的过程中 长为21的如果首先切成长为13 8的两块木板 则记开销为21 然后又将13的木板切成5 8 的木板 记记开销为 21+13=34 于是最终的开销记为34 输入切割的木板长度:N=3 L={8,5,8} 输出 34 解: 首先 模板的切割的顺序不确定 自由度很高 不过用贪心算法可以很快的解出来 其实就是求 哈夫曼的WPL 每一个叶子节点 对应切出的 L1 L2……木板 而每一个叶子节点的深度就对应着的切割需要的次数 ∴合计的开销=每个叶子节点的储存的数*对应的深度 哈夫曼形成的二叉树中 数最小的叶子节点 与 数其次小的叶子节点 为兄弟节点 且数最小的 一定也是深度最大的 依次从叶子节点向根靠拢每个节点对应的数一次越来越大 由于是求最小的点不妨将L 各项排序 每次将两个最小的合并最终得到的便是最优解复杂度O(N^2)
/*复杂度O(N^2)*/ # include <stdio.h> # include <stdlib.h> # include <time.h> void change(int *a,int *b);//交换函数 # define MAX 500 //木板的最长长度 # define N 200 //木板能锯的最大块数 __int64 SUM=0; //sum记录最小开销 int main(){ int L[N]={0},i,X,mina,minb,temp; srand(time(NULL)); X=rand()%N; //随机产生锯的木板数 for(i=0;i<X;i++) { L[i]=rand()%MAX+1; //随机数 printf("Ld== \n",i,L[i]); //输出随机数 } while(X>1) //直到最后合并的木板数量为1 { mina=0;minb=1; //初始的数组下标为0 1 if(L[mina]>L[minb]) //记录最小值 change(&mina,&minb); for(i=2;i<X;i++) if(L[i]<L[mina]) { minb=mina; mina=i; } else if(L[i]<L[minb]) minb=i; //经过循环得到两个最小值 temp=L[mina]+L[minb];//合并这两个最小值 SUM+=temp; if(mina==X-1) //当到达最后两块木板时 change(&mina,&minb); //交换 L[mina]=temp; //更新最小值 L[minb]=L[--X]; } printf("MIN=%I64d\n",SUM); return 0; } void change(int *a,int *b) { int temp=*a; *a=*b; *b=temp; } 若用最小堆 则O(NlogN) 堆实现 # include <stdio.h> # include <stdlib.h> # include <time.h> int DelMin(int Tree[]);//Tree[0]用来存储当前堆的树木 Tree[1]开始存数 void insert(int Tree[],int X);//向Tree数组堆里插入X # define MAX 500 //木板的最长长度 # define N 200 //木板能锯的最大块数 __int64 sum=0; //sum记录最小开销 int main(){ int L[N+1]={0},i,n,A,B;//L数组表示堆 scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&A); insert(L,A); } while(L[0]>1) { A=DelMin(L); B=DelMin(L); sum+=A+B; insert(L,A+B); } printf("%I64d\n",sum); return 0; } void insert(int Tree[],int X)//向Tree堆里插入X { int par,i=++Tree[0]; //插入X 后 Tree[0]+1 while(i>1) //直到i不是根节点 { par=i/2; //父节点为par if(Tree[par]<=X) break;//如果父节点满足最大堆的特性 则插入当前的位置即可 Tree[i]=Tree[par]; //否则调整堆 即位置上移 i=par; } Tree[i]=X;//插入新节点 } int DelMin(int Tree[])//删除最大值 { int i=1,root=Tree[1],R,L,X=Tree[Tree[0]--];//X记录当前末尾节点 root为根 即为最大值 if(Tree[0]<0) return -1; while(i*2<=Tree[0]) { L=i*2; R=L+1;//Left Right 记录左右节点 if(R<=Tree[0]&&Tree[R]<Tree[L])L=R; if(Tree[L]>=X) break;//如果所有的位置已经调整好 跳出循环 Tree[i]=Tree[L];//否则继续调整堆 i=L; } Tree[i]=X; return root; }以上的就是优先队列的应用 以上为最小堆下面是最大堆的应用 就几行不一样
题目:
POJ 2431 Expedition 你需要驾驶一辆卡车行驶L距离 最开始时，卡车上有P的汽油，卡车每开1单位距离需要消耗1单位的汽油。 在途中有N个加油站，第i个加油站在距离起点Ai距离的地方， 最多可以给卡车加Bi汽油，假设卡车的容量是无限大的， 无论加多少油都没有问题。求卡车到达终点需要加的最少的汽油。 限制条件: N∈[1,10000]; L,P∈[1,1000000]; Ai,Bi∈[1,100] 思路： 假设他们的车可以瞬间移动到之前到达过段任意加油站加油。 将油用光顺移回到MAX加油站加油再顺移回来 与直接经过MAX加油站的时候加油并走到没有油 这两种情况效果等价。 我们可以每次走到用光油，在瞬移回到之前经过的这段的加油站中 油最多的地方加油，继续往前走，用光继续瞬移找经过的剩下的油最多段地方加油…… 直到到达城市 EG： 油1 油2 油3 __车_____20________150_______100_________车_________ t t+1 上图中 车在t时刻到t+1时刻经过了三个油站 在t+1时刻油用光了 那么 如果在t——》t+1时刻取最大的油2站加油 则车在t+1时刻的地点向右又可行驶150的油的路程 此时得到的路程是最多的 如果车加了150的油后在 t+1时刻向右没有经过石油站 且没到终点 则车一定到达不了 这需要用到优先队列<堆> 堆实现 总复杂度O(NlogN) EG： 输入 N=4 L=25 P=10 A={10,14,20,21}; B={10,5,2,4}; 输出 2 （在第一个和第二个站加油） 代码用的数组Q表示堆
# include <stdio.h> # define MAX 1000 void insert(int Tree[],int X);//插入元素X int Delmax(int Tree[]);//删除堆最大值 int Q[MAX+1];//数组Q表示最大堆 Q[0]用来存储当前堆存取的数的数量 Q[1]开始存数 int main(){ int L,P,N,A[MAX+1]={0},B[MAX+1]={0}; int i,sum=0,local=0,oil=0,dis;//sum为加油的次数 local为当前的位置 oil为油箱中汽油的量 scanf("%d %d %d",&N,&L,&P); for(i=0;i<N;i++) scanf("%d",&A[i]); for(i=0;i<N;i++) scanf("%d",&B[i]); oil=P; A[N]=L;; //为了方便把终点当作加油量为0的加油站 for(i=0;i<=N;i++) { dis=A[i]-local;//接下来要行进的距离 while(oil<dis)//当剩余的油量小于接下来要行驶的距离 { if(!Q[0])//如果队列空 { printf("-1\n"); return 0; } oil+=Delmax(Q);//油量加上最大值 sum++; } oil-=dis;//油量减去当前行驶的距离 local=A[i];//地点到达A[i] insert(Q,B[i]); } printf("%d\n",sum);//因为终点当作了一个加油站 所以sum要减一 return 0; } void insert(int Tree[],int X)//向Tree堆里插入X { int par,i=++Tree[0]; //插入X 后 Tree[0]+1 while(i>1) //直到i不是根节点 { par=i/2; //父节点为par if(Tree[par]>=X) break;//如果父节点满足最大堆的特性 则插入当前的位置即可 Tree[i]=Tree[par]; //否则调整堆 即位置上移 i=par; } Tree[i]=X;//插入新节点 } int Delmax(int Tree[])//删除最大值 { int i=1,root=Tree[1],R,L,X=Tree[Tree[0]--];//X记录当前末尾节点 root为根 即为最大值 while(i*2<=Tree[0]) { L=i*2;R=L+1;//Left Right 记录左右节点 if(R<=Tree[0]&&Tree[R]<Tree[L])//比较两个子节点的值的大小 L=R; if(Tree[L]<=X) break;//如果所有的位置已经调整好 跳出循环 Tree[i]=Tree[L];//否则继续调整堆 i=L; } Tree[i]=X; return root; } 接下来就是堆排序了 /*建好最大堆或最小堆 然后一个一个删除 最后在用另一个数组承接删除的值 新数组即为排好序的 复杂度 时间O(NlogN) 空间O(N); */ # include <stdio.h> # include <stdlib.h> # include <time.h> # define MAX 100001 void insert(int Tree[],int X);//插入元素X int Delmin(int Tree[]);//删除堆最小值 int main(){ int A[MAX]={0},B[MAX]={0},i,n; scanf("%d",&n); srand(time(NULL)); for(i=1;i<=n;i++) insert(A,rand()@00001);//生成0--4000000内的随机数 i=0; while(A[0]) B[i++]=Delmin(A);//升序降序就看储存的B数组向哪个方向了 for(i=0;i<n;i++) printf("%d ",B[i]); return 0; } void insert(int Tree[],int X)//向Tree堆里插入X { int par,i=++Tree[0]; //插入X 后 Tree[0]+1 while(i>1) //直到i不是根节点 { par=i/2; //父节点为par if(Tree[par]<=X) break;//如果父节点满足堆的特性 则插入当前的位置即可 Tree[i]=Tree[par]; //否则调整堆 即位置上移 i=par; } Tree[i]=X;//插入新节点 } int Delmin(int Tree[])//删除最大值 { int i=1,root=Tree[1],R,L,X=Tree[Tree[0]--];//X记录当前末尾节点 root为根 即为最小值 while(i*2<=Tree[0]) { L=i*2;R=L+1;//Left Right 记录左右节点 if(R<=Tree[0]&&Tree[R]<Tree[L])//比较两个子节点的值的大小 L=R; if(Tree[L]>=X) break;//如果所有的位置已经调整好 跳出循环 Tree[i]=Tree[L];//否则继续调整堆 i=L; } Tree[i]=X; return root; } 只要把insert 和del函数记住堆就好办了