P5462 X龙珠
题面
这道题做得我七窍生烟.
一开始毫不犹豫地打了个\(vector\)来模拟,结果理解错了字典序的概念,惨得\(20\)分.\(4\)个 \(WA\) \(4\)个 \(TLE\).
然后觉得\(vector\)太慢了,写了一个双向链表.
在wty大佬的毒奶之下,惨得\(60\)分,\(4\)个 \(TLE\).
最后加了一个优先队列优化,总算\(A\)了这道题.
题意分析
从一串数里取出连续的两个数并去除掉取走后的空隙,放在另一个队列尾部,输出字典序最大的组合.
同志们每次让大的数尽量排在前面,因为是字典序,按位比较,满足贪心策略.
用一个优先队列,存一个双关键字,第一关键字是数的大小,第二关键字是数的编号.
用一个双向链表记录某个位置的数的前驱和后驱结点,每次取走数字的时候更新第一个数字的前驱的后驱,更新第二个数字的后驱的前驱,实现清除拿走之后空隙的目的.
代码
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "queue"
#include "map"
#include "vector"#define ll long long
#define INF 2147483647
#define debug(x) printf("debug:%lld\n",x)using namespace std;priority_queue<pair<ll,ll> >q;ll n,tot;
ll num[100010],to[100010],from[100010];
bool flag[100010];signed main(void)
{scanf("%lld",&n);tot=n;for(ll _=1;_<=n;_++){scanf("%lld",num+_);q.push(make_pair(num[_],_));}for(ll _=0;_<=n+1;_++){to[_]=_+1;from[_]=_-1;}while(tot){ll id1=q.top().second;ll id2=to[id1];q.pop();if(flag[id1]==true||flag[id2]==true||to[id1]==n+1){continue;}printf("%lld %lld ",num[id1],num[id2]);to[from[id1]]=to[id2];from[to[id2]]=from[id1];flag[id1]=true;flag[id2]=true;tot-=2;}
return 0;
}