自动搬运

查看原文

来自洛谷，原作者为

	Y25t 我从来没觉得打算法竞赛开心过。

搬运于2025-08-24 22:23:16，当前版本为作者最后更新于2020-11-26 16:38:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我们考虑第一个乱选的人，如果他选到的是他本来喜欢的汉堡（$b_1$），那么后面的人一定都能选到自己喜欢的汉堡。

若不然，假设他选到的汉堡是 $x$，那么下一次选不到自己喜欢的汉堡的人一定是喜欢 $x$ 的人中排在最后的那个（记作 $r_x$）。此时，剩下的汉堡为 $b_1,b_{r_x+1},\ldots,b_n$。并且第 $r_x$ 个人开始乱选。这就相当于原问题一个子问题。

记 $f_x$ 为从第 $r_x$ 个人开始乱选，剩余的汉堡为 $b_1,b_{r_x+1},\ldots,b_n$ 时 Josh 拿到他喜欢的汉堡的概率，特别地，$f_{b_1}=1$。记 $f_0$ 为答案，$r_0=1$。记 $s_{i,x}$ 为 $b_i,\ldots,b_n$ 中 $x$ 的个数，那么：

$$f_x=\sum_{y\neq x}\frac{s_{r_x+1,y}+[y=b_1]}{n-r_x+1}*f_y $$

我们就可以得到一个 $O(M^2+N)$ 的做法。

稍加观察我们发现，若把 $b_{r_x}$ 当作 $b_1$，那么 $f_x$ 就等于 $i$ 从 $r_x$ 到 $n$ 的 $f_{b_i}$ 的加权平均。

从后往前遍历所有 $r_x$，记录下 $f_{b_i}$ 的后缀和，就可以 $O(N)$ 得到答案了。

代码（因为对 $r_i$ 进行了排序，所以此代码复杂度为 $O(N+M\log M)$）：

#include<cstdio>
#include<algorithm>
#define N 1000005
#define M 500005
#define lf double

int n,a[N];

int m,r[M],pos[M];

lf f[M],sum;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		r[a[i]]=i;
		m=std::max(m,a[i]);
	}
	if(a[1]==a[n]){
		puts("1");
		return 0;
	}
	std::sort(r+1,r+m+1);
	for(int i=1;i<=m;i++)
		pos[a[r[i]]]=i;
	r[0]=1;
	sum=1;
	for(int i=m-1,j=n;i>=0;i--){
		if(r[i]==0)
			continue;
		while(j>r[i]){
			sum+=(a[j]==a[1]?1:f[pos[a[j]]]);
			j--;
		}
		f[i]=sum/(n-r[i]+1);
	}
	printf("%.15lf\n",f[0]);
}