自动搬运

查看原文

来自洛谷，原作者为

	Daben1 ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็

搬运于2025-08-24 22:23:21，当前版本为作者最后更新于2022-07-06 22:58:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路分析：

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

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

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

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

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

它们分别是：

1. $a[i] = a[i-1]$ 那么插入最大值和最小值。
2. $a[i] > a[i-1]$ 那么插入两个最大值。
3. $a[i] < a[i-1]$ 那么插入两个最小值。

当 $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;
}