题解：P12193 [NOISG 2025 Prelim] Ducks And Buttons

zhanghq2012 · 2025-04-15 14:08:32 · 题解

这道题也是一道送命题；

思路

已知每个单元格上都有一个小小的按钮，我们需要移动鸭子,如果在某一时刻在第 i 个单元格上有不少于 a_i 只小黄鸭，那么该单元格上的按钮就会被永久按下。

题目中让我们求最大值，我们只需要从后往前寻找最大值，将这些最大值相加到一个值里面累加。

对了别忘了用longlong

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[200005], maxn[200005], ans;

signed main()
{
    int n, d;
    cin >> n >> d;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int i = n; i >= 1;i--)
    {
        maxn[i] = max(maxn[i + 1], a[i]);
    }
    for(int i = 2; i <= n; i++)
    {
        ans += maxn[i];
    }
    cout << ans << endl;
    return 0;
}