题解：P13364 [GCJ 2011 Qualification] GoroSort

MatrixGroup · 2025-10-24 15:56:06 · 题解

题解

不妨假设策略最终排好序次数的期望存在，否则没有讨论的意义。

对于任何策略，考虑它一次对于一个排列的操作对不动点个数带来的影响。假定选取了 m 个位置，其中 p 个原本就是不动点，q 个在排列后（这个位置）可能是不动点。根据期望的线性性，期望增加的不动点个数是 q/m-p\le 1。且若每次选取所有未归位的点，这个数恰好是 1。

直觉上每次减少不超过 1 那么一定至少要这么多次才能归位，可以用鞅来严谨化这一点。

考虑令 c_k 为表示 k 步之后未归位的点个数，则根据上文可以验证 d_k=c_k+k 是一个下鞅。定义停时 T 为第一次 c_k=0 的时候。（也就是排好序的时候）根据假设，\mathbb E[T] 存在。并且，因为 0\le c_k\le n，有 |d_k-d_{k+1}|\le n+1 恒成立。因此停时定理的条件成立！可以利用下鞅的停时定理得到 \mathbb E[d_T]\ge \mathbb E[d_0]，化简可得 \mathbb E[T]\ge c_0，而 c_0 表示初始未归位的点的个数。特别的，在策略“每次选取所有未归位的点”中，这个下鞅是一个鞅，等式取等。因此答案为 c_0。

代码

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    print('Case #%d: %d'%(_+1,sum(a[i]!=i+1 for i in range(n))))