题目描述
难度分:$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;
}