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 奖励。
创建: 1 年,3 月前.
修改: 1 年,3 月前.
最后提交: 1 年前.
来源: N/A