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

lailai0916 · 2023-05-12 19:02:10 · 题解

解题思路

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

C_1\ge C_2\ge C_3\ge\dots\ge C_{n-2}\ge C_{n-1}\ge C_n

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

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

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