1 条题解
-
0
给定一个长度为 的序列 ，有以下操作：
- 选择一个区间 ，将其中的元素都加上 ；
求使 单调不减的最小操作次数。
答案就是 。
对于 ，如果 ，那么肯定要以 操作 次。右端点肯定是 最优，否则可能使得 ，徒增了操作次数。
CODE
#include <bits/stdc++.h> using namespace std; #define int long long inline int read() { int x = 0, f = 0; char c = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar(); return f ? -x : x; } #define INF (1e9 + 7) int a[200010]; signed main() { for (int T = read(); T --;) { int n = read(), res = 0; for (int i = 1; i <= n; i ++) { a[i] = read(); res += max(0ll, a[i - 1] - a[i]); } printf("%lld\n", res); } return 0; }让我 1min AC 了，开心
- 1
