龙珠游戏

题目

解析

显然有 O ( n 2 ) O(n^2) O(n2)贪心，但是显然不能AC
考虑利用数据结构优化，发现只有一个问题：
当前最优解可能已经在之前的贪心中使用，需要及时排除
显然二叉堆的懒惰删除法就适用于这个问题
查询下一个不能暴力，否则还是可以卡掉
很简单维护一个单向链表就好了

code:

#include
#include
#define mp make_pair
using namespace std;
int a[100010],nxt[100010],n;
bool vis[100010];
bool operator< (const pair<int,int> x,const pair<int,int> y){return x.first<y.first;}
priority_queue <pair<int,int> > q;
pair<int,int> o2;
int main()
{scanf("%d",&n);for(int i=1;i<n;++i)scanf("%d",&a[i]),nxt[i]=i+1,q.push(mp(a[i],i));scanf("%d",&a[n]);for(int i=(n>>1);i;--i){o2=q.top(),q.pop();if(vis[o2.second]){++i;continue;}while(vis[nxt[o2.second]]&&nxt[o2.second])nxt[o2.second]=nxt[nxt[o2.second]];if(!nxt[o2.second]){++i;continue;}printf("%d %d ",o2.first,a[nxt[o2.second]]);vis[o2.second]=vis[nxt[o2.second]]=1;}return 0;
}

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