P12193 题解

题目大意

这道题目描述了一个一维网格上的游戏，有

n

个单元格排成一行，每个单元格有一个按钮。初始时第

1

个单元格有

d

只鸭子。当某个单元格

i

上的鸭子数量不少于

a[i]

时，该单元格的按钮会被永久按下。

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

解题思路

关键分析

移动的本质：每只鸭子从单元格 $1$ 移动到单元格 $i$ 需要 $(i-1)$ 次移动。如果有 $k$ 只鸭子移动到 $i$ ，那么总移动次数为 $k×(i-1)$ 。
需求传递性：每次移动的鸭子需要保证后面所有按钮均可被按下，所以需要从长远看移动的鸭子数量。

核心思路

对于每个单元格 $i$ （ $i≥2$ ），有足够多的鸭子从其左侧移动过来满足 $a[i]$ ；
这些移动的鸭子可以继续向右移动满足更右侧单元格的需求；
因此，对于每个 $i$ ，我们需要计算从其左侧移动过来的鸭子数量的"累积最大值"。

具体算法

从右向左预处理一个数组 $f$ ，其中 $f[i]$ 表示为了满足单元格 $i$ 及其右侧所有单元格的需求，至少需要有多少只鸭子从左侧移动到 $i$ 。
$f[n] = f[n]$ （最右侧单元格只需满足自身需求）。
对于 $i$ 从 $n-1$ 到 $2$ ， $f[i] = \max(a[i], f[i+1])$ （取当前需求和右侧需求的较大值）。
最终结果为所有 $f[i]$ （ $i$ 从 $2$ 到 $n$ ）的和，因为每只移动到 $i$ 的鸭子需要 $(i-1)$ 次移动，而总移动次数就是 $\sum f[i]×1 = \sum f[i]$ （因为每只鸭子移动 $1$ 次到 $2$ ， $2$ 次到 $3$ ， $\cdots$ ， $(n-1)$ 次到 $n$ ，但通过累积计算已经考虑了这些）。

参考代码

CPP

#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;
}

~ 完结撒花 ~

文章操作

题目大意

解题思路

关键分析

核心思路

具体算法

参考代码

相关推荐

评论

P12193 题解