16 人解决，29 人已尝试。
20 份提交通过，共有 104 份提交。
6.1 EMB 奖励。
单点时限: 1.0 sec
内存限制: 256 MB
有 $n$ 个士兵需要被排成一排。由于每两个士兵的身高都互不相同，因此我们用 $1,2,\cdots n$ 这 $n$ 个整数来分别表示他们的身高，不妨设第 $i$ 个士兵的身高为 $i$ ，$(1\le i\le n)$。
现在，队列中身高为 $1,2,\cdots m$ 的 $m$ 个士兵的位置已经确定，你需要确定剩下 $n-m$ 个士兵的位置，确定完毕之后，你得到一个士兵的队形： $p_1,p_2,\cdots p_n$ 。
接下来，首长会从你编排的队形中等概率随机抽取一个连续的区间 $(l,r)$ ，$1\le l\le r\le n$，他会检查 $p_l,p_{l+1},\cdots p_r$ 这个区间的士兵们能否组成一列良好的小队。一列士兵被称为良好的小队，当且仅当他们中最高的一个士兵站在排头或者排尾。例如，当 $n=5$ 时，如果士兵的队形是 $1,3,5,2,4$ ，那么当首长抽取 $(1,3)$ 时，就得到一支良好的小队，因为 ${1,3,5}$ 中最高的士兵处于排尾 ；当首长抽取 $(3,5)$ 时，也得到一支良好的小队，因为 ${5,2,4}$ 中最高的士兵处于排头；而当首长抽取 $(2,4)$ 时，就不能得到一支良好的小队，因为 ${3,5,2}$ 中最高的士兵既不处于排头也不处于排尾。
你希望首长在抽查的时候抽中一列良好的小队的概率尽可能大，请你给出最优的编排方案。
首先输入一个正整数 $T$ ，表示数据组数。
对于每组数据：
第一行，两个整数 $n,m$ ，分别表示士兵的总数目以及已经确定位置的士兵数目。
第二行， $n$ 个整数，第 $i$ 个数表示 $a_i$ ，如果 $a_i=0$ 则表示第 $i$ 个位置的士兵还没有被确定；如果 $a_i\ne 0$ 则表示第 $i$ 个位置的士兵是 $a_i$ 号士兵（即他的身高为 $a_i$）。数据保证恰有 $m$ 个位置满足 $a_i\ne 0$ 。
保证 $T$ 组测试数据的 $\sum n$ 不超过 $500$ 。
对于每组数据，输出一行，$n$ 个整数 $p_1,p_2\cdots p_n$ 表示你编排的士兵队形，整数之间用一个空格隔开，最后一个整数后应当紧跟一个换行，而不允许有行末空格。你的队形必须是一个 $1,2,\cdots n$ 组成的排列，并且对于任意的 $1\le i\le n$ ，若输入数据中 $a_i$ 不为 $0$ ，则必须有 $p_i=a_i$ 。你的答案需要在满足限制的情况下最大化首长抽中良好小队的概率，如果有多种合法的方案，你可以输出任何一种。
3 3 0 0 0 0 4 1 0 1 0 0 10 4 0 3 0 0 1 0 0 4 0 2
1 2 3 2 1 3 4 10 3 9 8 1 7 6 4 5 2
【数据范围】
$1\le T \le 500$
$1\le n\le 500,0\le m\le n,\sum n \le 500$，$0\le a_i \le m$ ，对于任意的 $1\le i,j\le n$ 若满足 $a_i\ne 0,a_j\ne 0,i\ne j$ 则必有 $a_i\ne a_j$ 。
16 人解决，29 人已尝试。
20 份提交通过，共有 104 份提交。
6.1 EMB 奖励。
创建: 10 月前.
修改: 10 月前.
最后提交: 7 月，3 周前.
来源: N/A