思路基本全部正确，但是棋差一着，没有注意到转移点只有一个。
说明所谓的思维题，并没有那么不可做。
题意：对于一个长度为
的正整数序列
，定义一次操作为：选出最小值所在的位置（多个则任取），将下标加入 序列的末尾，并将对应位置 。
我们做了 次操作，得到了序列
。现在你知道序列 ，须求出是否存在一个初始序列 能得到这个 ，存在则输出字典序最小解。
。
观察一个
序列在操作过程中发生的变化。
我们发现，我们会先把当前所有的最小值 ，然后再取出当前的所有最小值，再全部
。
因此，我们定义 为第 次操作前的序列最小值，那么 。
的变化有明显的分段特征，我们考虑把 序列分段，每段的 都是一样的。
稍微手玩一下可以得到分段方案合法的充要条件：
除最后一段外，每段中出现的元素集合都必须包含上一段出现的所有元素。这也等价于必须包含这一段之前出现的所有元素。
最后一段我们等会考虑，先考虑前面的段。
我们考虑对于一个右端点 ，什么样的左端点 可以使
被分为合法段，显然，这与其他的段怎么划分是没有关系的。
首先，
中出现的元素，都必须在
中出现。同时，
中不能出现重复的元素。
设 中有 个不同元素，那么 要么是 ，要么无解。这说明对于每个 只有最多一个合法的 。
而对于最后一段而言，它合法只需要没有重复元素即可。
上述结论表明，如果我们确定了最后一段的端点，前面的划分方案是唯一的。
那么我们如何确定这个点，使得字典序最小？
考虑去掉最后一段之后，所有点在操作完后应该全部相等，那么我们当然让前面的段数越少越好（因为每个点被加几次已经确定了），在段数相等的条件下，我们会选择尽量靠后的点，因为最后一段相当于在这个“相等"的值上额外
，我们当然要让这个 越少越好。
确定这个点之后，反推出初始方案即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5,inf = 0x3f3f3f3f;
int n,k;
int b[N],a[N];
int f[N],lst[N],ton[N];
int main()
{
cin >> n >> k;
for(int i = 1;i <= k;i++) cin >> b[i];
int pre = 0;
for(int i = 1,cnt = 0;i <= k;i++)
{
pre = max(pre,ton[b[i]]);
if(!ton[b[i]]) ++cnt;
ton[b[i]] = i;
if(i - pre == cnt) f[i] = f[pre] + 1;
else f[i] = inf;
}
int p = k;
memset(ton,0,sizeof ton);
for(int i = k;i >= 1;i--)
{
if(ton[b[i]]) break;
ton[b[i]] = true;
p = i;
}
int Mn = -1;
for(int i = p - 1;i < k;i++)
if(Mn == -1 || f[i] <= f[Mn]) Mn = i;
if(f[Mn] >= inf) return puts("-1"),0;
for(int i = 1;i <= n;i++) a[i] = f[Mn] + 1;
for(int i = 1;i <= Mn;i++) a[b[i]]--;
for(int i = 1;i <= n;i++) printf("%d ",a[i]);printf("\n");
return 0;
}
|