CodeForces - 1330E Drazil Likes Heap(贪心)

题目链接：点击查看

题目大意：首先定义 n 阶完全大顶堆的概念，就是满足节点个数恰好为个，序号从 1 开始排列，对于每个节点 i 都满足

接下来给出一段伪代码，教你如何从大顶堆中删去节点 i 

最后给你一个 h 和一个 g ，其意义是，现在有一个 h 阶的完全大顶堆，要求恰好删除掉个结点后，使得剩下一个 g 阶的完全大顶堆，满足：

g 阶完全大顶堆的结点为 1 ~ 

个结点权值和最小

给出一种合适的删除方案，使得满足题意

题目分析：重点就是读题了吧，读懂题会发现其实就是一个贪心，题目给出的伪代码的操作是：

删除结点 a[ i ] 的值

用结点 i 较大的子节点填充到结点 i 的位置，继续向下递归

因为是大顶堆，所以从点 1 开始正向遍历，如果对于某个节点 i 来说，节点 i 的子树的绝对高度大于了最后需要保留的高度，那么说明节点 i 的子树中必须删除掉一些节点才能保证降低子树的高度，而对于这棵子树来说，a[ i ] 一定是子树中的最大值，所以删掉节点 i 一定是最优的，所以一层 for 带着一个 while 贪心删就好了，最关键的核心代码就是大顶堆的删除，但是题目给出了伪代码。。真是让人匪夷所思的题目

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=(1<<21)+100;int a[N];int get_id(int k) {if(!a[k<<1]&&!a[k<<1|1])return k;if(a[k<<1]>a[k<<1|1])return get_id(k<<1);elsereturn get_id(k<<1|1); }void dfs(int k) {if(!a[k<<1]&&!a[k<<1|1])a[k]=0;else if(a[k<<1]>a[k<<1|1]){a[k]=a[k<<1];dfs(k<<1);}else{a[k]=a[k<<1|1];dfs(k<<1|1);} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int h,g;scanf("%d%d",&h,&g);for(int i=1;i<1<<(h+1);i++)a[i]=0;for(int i=1;i<1<<h;i++)scanf("%d",a+i);vector<int>ans;int limit=(1<<g)-1;for(int i=1;i<1<<g;i++)while(get_id(i)>limit){ans.push_back(i);dfs(i);}LL sum=0;for(int i=1;i<1<<g;i++)sum+=a[i];printf("%lld\n",sum);for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);puts("");}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1330E Drazil Likes Heap(贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。