P12193 题解

· · 题解

题目大意

这道题目描述了一个一维网格上的游戏，有 n 个单元格排成一行，每个单元格有一个按钮。初始时第 1 个单元格有 d 只鸭子。当某个单元格 i 上的鸭子数量不少于 a[i] 时，该单元格的按钮会被永久按下。

我们要通过移动鸭子（每次移动一格）使得所有按钮都被按下，求最少的总移动次数。

解题思路

关键分析

  1. 移动的本质：每只鸭子从单元格 1 移动到单元格 i 需要 (i-1) 次移动。如果有 k 只鸭子移动到 i，那么总移动次数为 k×(i-1)。

  2. 需求传递性：每次移动的鸭子需要保证后面所有按钮均可被按下，所以需要从长远看移动的鸭子数量。

核心思路

  2. 对于 i 从 n-1 到 2，f[i] = \max(a[i], f[i+1])（取当前需求和右侧需求的较大值）。

  3. 最终结果为所有 f[i]（i 从 2 到 n）的和，因为每只移动到 i 的鸭子需要 (i-1) 次移动，而总移动次数就是 \sum f[i]×1 = \sum f[i]（因为每只鸭子移动 1 次到 2，2 次到 3，\cdots，(n-1) 次到 n，但通过累积计算已经考虑了这些）。

参考代码

#include<bits/stdc++.h>
#define int long long  // 使用long long防止溢出
using namespace std;

const int MAXN = 2e5 + 5;  // 设置最大数组大小
int n, d;                  // n-单元格数，d-初始鸭子数
int a[MAXN], f[MAXN];     // a-需求数组，f-预处理数组

signed main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(0);
    cout.tie(0);

    // 输入读取
    cin >> n >> d;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 从右向左预处理f数组
    // f[i]表示为了满足i及其右侧所有单元格的需求，
    // 至少需要有多少只鸭子从左侧移动到i
    f[n] = a[n];  // 最右侧单元格只需满足自身需求
    for(int i = n-1; i >= 2; i--) {
        // 当前单元格的需求和右侧单元格需求的较大值
        f[i] = max(a[i], f[i+1]);
    }

    // 计算总移动次数
    // 每只移动到i的鸭子需要(i-1)次移动
    // 但通过f数组的累积计算，f[i]已经考虑了所有移动
    int ans = 0;
    for(int i = 2; i <= n; i++) {
        ans += f[i];
    }

    cout << ans << '\n';
    return 0;
}

~ 完结撒花 ~