锐客网

  1. 首页 > it技术 > >

Omkar and Waterslide

题解

题意：给出一个数字序列，有这么一种操作：使得一段递增ai<=a(i+1)的连续序列都+1，问最少需要多少次操作才可以使得整个数字序列都满足(ai<=a(i+1))
简单思路：我们应该寻找这样一种连续子序列，使得这段序列中的数字都小于最前端的前一个数字和最后端的后一个数字，为将这段序列改造的满足要求，我们最少需要操作的次数是最前端的前一个数字-这段序列中最小的数字。
【Omkar and Waterslide】这里我们可以将暴力寻找稍作简化，我们不断让ans+=max(0,ai-a(i+1)),如果是递增的那么答案不变化，如果ai>a(i-1),我们可以通过ai-a(i+1)次操作使得以a(i+1)开始的递增序列小于上一个递增序列的数都等于上一递增序列的最大的数。

#include #includeusing namespace std; const int N = 2e5 + 100; typedef long long ll; ll arr[N]; int main() { int t; cin >> t; while (t--) { ll n,ans=0; cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; } for (int i = 1; i < n; i++ ) { ans += max(arr[i] - arr[i + 1], 0ll); } cout << ans << endl; } }

    推荐阅读


    上一篇：补题|Omkar and Bed Wars

    下一篇：Omkar and Infinity Clock