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

原题链接

• 洛谷 P9280 [AGM 2023 资格赛] Monty Hall

解题思路

1. 对于 $\forall i\in[1,n-1]$，都有 $C_i\ge C_{i+1}$，即 $C_1\ge C_2\ge C_3\ge\cdots\ge C_{n-2} \ge C_{n-1}\ge C_n$。

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

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

3. 还剩 $n-1$ 个门，需要 $n-1$ 步，所以最少花费的总代价为 $(n-1)\cdot C_{n-1}+C_n$。

参考代码

#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]*1ll*(n-1)+c[n]<<'\n';
	return 0;
}