[题解]P5462-X龙珠

· · 题解

观察题目，思考一下，很快可以知道，这题使用贪心即可。

题目要求求字典序最大的方案，则

越大的数字应该放在越前面，最大的数字放在最前面。

所以前面的要尽量大，我们这里以每次取出的两颗龙珠前者为准（因为他排在前边嘛）

题目规定各龙珠编号互不相同，那么最终摆放顺序直接就确定了。 从大到小排序，一波扫过来，如果未被取走一并取出与其相邻的下一颗龙珠，已经取走的就不管了，完事。

这里有个特殊点，最后一颗龙珠需要特判，因为她(?)没有下一颗龙珠与其作伴。

至于删除的问题，咱就直接链表啥的解决了吧。。。比赛的时候因为写不好链表罚分到自闭

（不会链表的可以先去看看）

程序的思路：

输入\Rightarrow 建链表\Rightarrow排序（大到小）\Rightarrow循环\{取出龙珠 \Rightarrow 输出\}

这里我搞了一个pos用于储存一个数在原链表中的位置（因为编号各不相同）

下面是码，

#include<bits/stdc++.h>
using namespace std;

int N;
int a[1000005];//原数列（位置=>数值） 
int b[1000005];//表示这个数是否已经被取走 
int c[1000005];//排序好的数列 
int pos[1000005];//记录位置（数值=>位置） 
int n[1000005];//next记录链表结点的下一个节点位置 
int l[1000005];//last记录链表结点的下一个节点位置 

bool cmp(int x,int y) {//排序用的比较函数 
    return x>y;
}

int main() {
    cin>>N;
    for(int i=1; i<=N; i++) {
        cin>>a[i];
        pos[a[i]]=i;//位置 
        c[i]=a[i];//赋值 
        n[i]=i+1;//后继 
        l[i]=i-1;//前驱 
    }
    n[N]=-1;//最后一个结点指向-1（无） 
    sort(c+1,c+1+N,cmp);//排序 
    for(int i=1; i<=N; i++) {
        int k1,k2,p1,p2;//k为编号，p为位置 
        k1=c[i];//取出的前一个龙珠编号 
        p1=pos[k1];//前一个龙珠的位置 
        p2=n[p1];//后一个龙珠的位置（前者的下一个） 
        if(p2==-1)//如果这是最后一个龙珠是不能取下一个的 
            continue;
        k2=a[p2];//后一个龙珠的值 
        if(!b[k1] && !b[k2]) {//如果没被取出 
            cout<<k1<<" "<<k2<<" ";//输出 
            b[k1]=1;
            b[k2]=1;//标记 
            //删除2个相邻链表节点的操作： 
            n[l[p1]]=n[p2];//前者的下一个改成后者的下一个 
            l[n[p2]]=l[p1];//后者的上一个改成前者的上一个 
        }
    }
    return 0;//完事跑路 
}

理解第一，通过第二。

『做正确，好懂，好看的题解』