题目描述

难度分:$1200$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n$、$k$$(1 \leq k \leq n \leq 10^5)$和$k$个整数，范围$[-10^9,10^9]$。

这$k$个数是一个长为$n$的非降数组的前缀和的最后$k$项（从左到右）。

是否存在这样的非降数组？输出Yes或No。

输入样例

4
5 5
1 2 3 4 5
7 4
-6 -5 -3 0
3 3
2 3 4
3 2
3 4

输出样例

Yes
Yes
No
No

算法

贪心构造

可以利用前缀和的后$k$项先还原出原数组的后$k-1$项，检查它们是不是非递减的。

然后考虑极限情况，前$n-k+1$个元素都和倒数第$k-1$项相同。此时只需要前$n-k+1$项的和不小于$s[n-k+1]$即可（前缀和后$k$项的第$1$项），这说明前面的元素有变成非递减的操作空间。

复杂度分析

时间复杂度

总共遍历了两次数组，因此时间复杂度为$O(k)$。

空间复杂度

用了一个数组$a$来存储由前缀和数组$s$的后$k$项还原出来的数组后$k-1$项，因此额外空间复杂度为$O(k)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int t, n, k, s[N], a[N];

bool solve() {
    for(int i = 1; i <= k; i++) {
        scanf("%d", &s[i]);
    }
    if(k == 1) return true;
    for(int i = k; i >= 2; i--) {
        a[i] = s[i] - s[i - 1];
    }
    for(int i = 3; i <= k; i++) {
        if(a[i - 1] > a[i]) return false;
    }
    return (long long)(a[2] - a[1])*(n - k + 1) >= s[1];
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        if(solve()) {
            puts("Yes");
        }else {
            puts("No");
        }
    }
    return 0;
}