配对游戏

NC13333. 配对游戏

描述

美团点评是综合性生活服务平台，覆盖吃喝玩乐。在休闲娱乐版块，有很多轰趴、桌游、密室逃脱类的项目，适合多人一起玩。下面就是出自团队游戏场景中的一个问题。
有 n 个人排成一排，一开始全部面向前方，然后大家一起转身，随机朝左或是朝右转。
转身后，不断检查队列，如果存在两个面对面的相邻的人，则将这两个人从队列中消除；直到不存在两个面对面的相邻的人。
例如 > 表示向右， < 表示向左
队列“>>><<<”的消除过程为，“>>><<<”到“>><<”到“><”到“”（每次去除一对），最后剩下人数为0。
队列“>><><<<>”的消除过程为，“>><><<<>”到“>><<<>”到“><<>”到“<>”（每次去除一对)，最后剩下人数为2
求最后剩下人数的期望值。

输入描述

一行一个正整数 n (1 ≤ n ≤ 2000)。

输出描述

一行一个实数，表示剩下人数的期望值，四舍五入保留三位小数。

示例1

输入:

输出:

4.168

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 408K, 提交时间: 2021-12-03 19:08:47

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	double d[2021];
	d[0]=0;d[1]=1;d[2]=1.5;
	for(int i=3;i<=n;++i)
		d[i]=(d[i-1]*(i+1)-d[i-3]*(i-2)+d[i-2]*(i-3))/i;
		cout<<fixed<<setprecision(3)<<d[n];
}

Python3 解法, 执行用时: 44ms, 内存消耗: 4644K, 提交时间: 2023-04-03 19:32:29

n = int(input())
d=[0 for x in range(n+3)]
d[0] = 0
d[1] = 1
d[2] = 1.5
d[3] = 2
for i in range(4,n+1):
    d[i] = (d[i-1]*(i+1) + d[i-2]*(i-3)-d[i-3]*(i-2))/i
print('%.3f'%d[n])

上一题

下一题

详情