我构造错了, 本以为只要整个数组是个W形状就可以, 再多低谷画不出来了, 感觉很多低谷的时候不太对劲. WA了一发.

结果是用差分. a数组全变成0, 差分数组也全变成0!

每一次对原数组一整个区间 - k, 但是对于差分数组来说, 只有两头改变:

  1. a[1 ~ i] - 1 -> cnt[1] -= 1 and cnt[i + 1] += 1 (限制在这里, a[1]的大小, 限制了cnt[i + 1] += 1的次数)
  2. a[i ~ n] - 1 -> cnt[i] -= 1 and cnt[n + 1] += 1 (我们发现这一种操作, cnt[n + 1]完全没用!并且说明: cnt[i] > 0 的情况必定可以变成0!)

我们想要一个全0的差分数组, 首先观察上述两种操作, 从区间操作, 变成了单点操作!!! 第一种可以将 1 和 i + 1位置 + 1, 而第二种是将 i 位置 - 1, 第二种是没有限制的, 所以只需要统计第一种操作的次数(cnt[i]是负数的和), 然后比较原数组a[1]能否减这么多次, 这就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

int a[30010];
int cnt[300010];

int main() {
    int t;
    int n;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; i++) {
            cnt[i] = a[i] - a[i - 1]; //差分数组
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (cnt[i] < 0)
                sum += -1 * cnt[i];
        }
        cout << (sum <= a[1]? "YES" : "NO") << '\n';
        
    }
    return 0;
}