Skip to main content
Original166 words1 min

题解：P9280 [AGM 2023 资格赛] Monty Hall

Summary

环形排列 n 扇门，每次选 i 向右移动 i 步并打开落点处的门，选 i 的代价 C_i 随 i 增大而不增，求开完所有门的最小总代价。因代价随步长增大而变小，第一步选 n 绕一圈打开第 1 扇门，之后每步选 n-1 相当于向左退一格逐个开门，总代价为 n-1 乘以 C(n-1) 再加 C_n。时间复杂度 O(n)。

解题思路​

对于 ∀i∈[1,n−1]\forall i\in[1,n-1]，都有 Ci≥Ci+1C_i\ge C_{i+1}，即：

C1≥C2≥C3≥⋯≥Cn−2≥Cn−1≥CnC_1\ge C_2\ge C_3\ge\dots\ge C_{n-2}\ge C_{n-1}\ge C_n

所以每次选择的 ii 越大，所需的代价越小。具体方法如下：

  • 第一步选择 nn，向右移动 nn 步。因为门围成了一个环，所以转了一圈回到原位，并打开了第 11 扇门。
  • 后续每一步都选择 n−1n-1，向右移动 n−1n-1 步。等于向左移动 11，打开这扇门。

还剩 n−1n-1 个门，需要 n−1n-1 步，所以最少花费的总代价为：

(n−1)⋅Cn−1+Cn(n-1)\cdot C_{n-1}+C_n

参考代码​

186 Bcpp
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int c[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>c[i];
	cout<<c[n-1]*(n-1ll)+c[n]<<'\n';
	return 0;
}