Posted on 2010-04-05 10:04
Initiate 阅读(645)
评论(0) 编辑 收藏 引用 所属分类:
递归分治
Heap
|
Time Limit: 5000MS
|
|
Memory Limit: 131072K
|
|
Total Submissions: 1965
|
|
Accepted: 392
|
Description
A (binary) heap is an array that can be viewed as a nearly complete binary tree. In this problem, we are talking about max-heaps.
A max-heap holds the property that for each node than the root, it’s key is no greater than its parent’s. Upon this we further require that for every node that has two children, key of any node in the subtree rooted at its left child should be less than that of any node in the subtree rooted at its right child.
Any array can be transformed into a max-heap satisfying the above requirement by modifying some of its keys. Your task is find the minimum number of keys that have to be modified.
Input
The input contains a single test case. The test case consists of nonnegative integers distributed on multiple lines. The first integer is the height of the heap. It will be at least 1 and at most 20. Then follow the elements of the array to be transformed into a heap described above, which do not exceed 109. Modified elements should remain integral though not necessarily nonnegative.
Output
Output only the minimum number of elements (or keys) that have to be modified.
Sample Input
3
1
3 6
1 4 3 8
Sample Output
4
Hint
1 10
/ \ / \
3 6 =====> 3 9
/ \ / \ / \ / \
1 4 3 8 1 2 4 8
Source
POJ Monthly--2007.04.01, czh
题意理解：在原树上改变部分数字，使之满足以下两个条件：
1所有的节点的值都不会比他的父亲节点大
2左子树的所有节点的值都比对应的右子树小
所以，这里要求，左<右<=中
算法思想：递归后续遍历+最长上升字串算法nlogn
算法设计：用数组来存储树
后续遍历找到合适的排序
最长上升子序列，找到了最多的可利用部分
改动自然是最小的了。
注意的地方：为了使<和<=保持一致
每次从左到右的时候要减去1，后面所有的节点都受影响
这样只做一次不降子序列就行了。
源代码：(已AC)
1 #include<iostream>
2 using namespace std;
3 int h,n,p,tmp,SIZE;
4 int *a,*tre;
5 void maketre(int k)
6 {
7 if(2*k<=n)
8 maketre(2*k);
9 if(2*k+1<=n){tmp++;
10 maketre(2*k+1);
11 }
12 tre[++p]=a[k]-tmp;
13 }
14 int solve()
15 {
16 int l,r,mid,len=1;
17 a[1]=tre[1];
18 for(int i=2;i<=n;i++)//
19 {
20 l=1,r=len;
21 while(l<=r)
22 {
23 mid=(l+r)>>1;
24 if(a[mid]<=tre[i]) l=mid+1;//上升或不降
25 else r=mid-1;//二分查找
26 }
27 a[l]=tre[i];//插入
28 if(l>len) len++;//增加长度
29 }
30 return len;
31 }
32 int main()
33 {
34 scanf("%d",&h);
35 SIZE=1 << h;
36 a=new int[SIZE+100];
37 tre=new int[SIZE+100];
38 int t;
39 while(scanf("%d",&t)!=EOF)
40 a[++n]=t;
41 maketre(1);
42 cout<<n-solve()<<endl;
43 }
44
45
错误之处：
树不一定是满的，也就是说若只有左孩子的时候，左孩子是可以与父亲相等的……这个地方错了很多次
只能使用不降子序列，无法使用上升子序列？