P6721

Daben1 · 2022-07-06 22:58:47 · 题解

思路分析：

这道题，不需要用学吐了的树套树，推公式推三天的六边形插头动态规划等 高级的算法。

我们只需要一个朴素的算法，就是贪心。

首先我们可以看出，第一个数很明显不会变，所以直接输出即可。

由于要满足答案有效性，我们可维护一个最大值和一个最小值。

当 f[a[i]]=1（走过）有 3 种情况。

它们分别是：

当 f[a[i]]=0 (没走过)就先输出，再判断（ 2, 3 ）。

思路明确，贪心即可。

代码：

// C++20 + O2
#include<bits/extc++.h>
using namespace std;
int a[1000001],n,m,l,r;
bool f[1000001];//注意数据范围
void findl(){
    while(f[l]) l++; printf("%d ",l);
    f[l]=1; l++;
}
void findr(){
    while(f[r]) r--; printf("%d ",r);
    f[r]=1; r--;
}//两个函数维护一下最大值和最小值
int main(){
    scanf("%d",&n);//这题有点小卡，scanf还是保险点
    m=n*2-1,l=1,r=m;
    for(int i=1; i<=n; i++){//贪心开始
        scanf("%d",&a[i]);
        if(i==1){
            printf("%d ",a[i]);
            f[a[i]]=1;
            if(a[i]==1) l++;
        }else{
            if(f[a[i]]){
                if(a[i]==a[i-1]){
                    findl(); findr();
                }else
                if(a[i]>a[i-1]){
                    findr();findr();
                }else
                if(a[i]<a[i-1]){
                    findl();findl();
                }//分好三种情况
            }else{
                printf("%d ",a[i]);
                f[a[i]]=1;
                if(a[i]==r) r--;
                if(a[i]>a[i-1]) findr();
                if(a[i]<a[i-1]) findl();
            }//结果依次输出，完美结束
        }
    }
    return 0;
}