CCPC-Wannafly Winter Camp Day3 Div1

题目链接:https://zhixincode.com/contest/14/problem/A?problem_id=203

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

样例输入 1 

5
5 3 4 1 2

样例输出 1

3 4 2 5 1

 题解:

 首先例如 $p = [3,4,2,1]$,则 $A(p) = [3,3,2,1]$;然后相应的 $q = [4,3,1,2]$,长度为 $4$ 的前缀其中最小值为 $1$($A(p)_{4} = 1$),因此 $4$ 排在 $q$ 的第一位。

不难发现,一般来讲,长度越长的前缀,相应的在 $q$ 中应该排在越前面,但是如果出现长度长的前缀出现在长度短的前缀的后面呢?只可能是因为它们对应的 $A(p)_{?}$ 值是相等的,长度长的才会排后面。而且我们进一步可以发现,在 $q$ 中,若某一段是递增的,那么这一段是必然是连续的,这个靠反证一下就很容易证明。

因此我们可以将 $q$ 划分成若干段,每一段都是连续递增的,而前一段中任意数必然大于后一段中的任意数。

例如上面举的例子 $q = [4,3,1,2]$ 就可以分成 $[[4],[3],[1,2]]$,然后我们观察一下这个序列分成了三段,因此对应的 $A(p)$ 就只有三个数:${1,2,3}$,$A(p)$ 的第 $4$ 位是最小的,即等于 $1$;然后第 $3 $ 位是次小的,即$A(p)_{3} = 2$;然后排在最后的一段 $A(p)_{1} = A(p)_{2} = 3$ 是最大的。再然后,我们可以知道 $A(p)$ 是一个只会不严格单调递减的序列,相应地可以很容易推出字典序最小的 $p$。

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,q[maxn],p[maxn];
int main()
{
    scanf("%d",&n);
    int now=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&q[i]);
        if(i==1 || q[i-1]>q[i]) p[q[i]]=++now;
    }
    for(int i=1;i<=n;i++) if(!p[i]) p[i]=++now;
    for(int i=1;i<=n;i++) printf("%d ",p[i]);
}
原文地址:https://www.cnblogs.com/dilthey/p/10433139.html