【ybotj 高效进阶 4.1】【二叉堆】龙珠游戏

题目

解题思路

要取相邻的两颗龙珠
那么第一颗不能取最后一颗
所以一开始第n颗不能在二叉堆中排序
next数组标记下一个相邻龙珠的位置
每次取出最大的龙珠 不能是最后一个 以及ta相邻的一个
然后标记被取过，更新next数组

代码

#include
#include
using namespace std;
struct lzf{int z,w;
}tree[100200];
int n,t,a[100010],b[100010],next[100010];
void put(int x,int y)
{tree[++t].z=x;tree[t].w=y;int son=t;while (son>1){int fa=son/2;if (tree[son].z<tree[fa].z)return;swap(tree[son],tree[fa]);son=fa;}
}
void get()
{lzf res=tree[1]; tree[1]=tree[t--]; int fa=1;while (fa*2<=t){int son=fa*2;if (tree[son].z<tree[son+1].z&&son+1<=t) son++;if (tree[son].z<tree[fa].z) break;swap(tree[son],tree[fa]);fa=son;}if (b[res.w]==1) return get();  //被取过，再取一次while (b[next[res.w]]==1&&next[res.w]<=n)  //如果下一个被取过，继续往后取next[res.w]=next[next[res.w]];if (next[res.w]>n) return get();  //第二个没得取，再取一次printf("%d %d ",a[res.w],a[next[res.w]]);  b[res.w]=b[next[res.w]]=1;  //标记被取过
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);next[i]=i+1;if (i!=n) put(a[i],i);else {tree[++t].z=a[i];tree[t].w=i;  //第n颗进入二叉堆，不用维护}}for (int i=1;i<=n/2;i++) get();return 0; 
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！