题目描述

难度分:$1300$

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

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，长为 $n$的数组$b(1 \leq a[i] \leq 10^9)$。

你可以执行如下操作任意次：

• 选择一个下标$i$，满足$a[i] \leq a[(i+1)\%n]$，然后把$a[i]$增加$1$。

能否把$a$变成$b$？输出YES或NO。

输入样例

5
3
1 2 5
1 2 5
2
2 2
1 3
4
3 4 1 2
6 4 2 5
3
2 4 1
4 5 3
5
1 2 3 4 5
6 5 6 7 6

输出样例

YES
NO
NO
NO
YES

算法

贪心

由于只能对$a$数组中的元素进行自增操作，因此如果存在$a[i] \gt b[i]$的下标$i$，肯定就无解了。而$a[i]=b[i]$的下标不用管，所以只需要去考虑$a[i] \lt b[i]$的下标。

而$a[i]$要想变成$b[i]$，那$a[i+1]$至少就要是$b[i]-1$，因此我们检查$b[i]-1$会不会超过$b[i+1]$就行了。如果超过了，说明$a[i+1]$要变成一个大于$b[i+1]$的数才能使得$a[i]$变成$b[i]$，但$a[i+1]$就永远不可能变成$b[i+1]$了。（以上讨论中，当$i=n$时，满足$i+1=1$）

综上，当$b[i]-1 \leq b[i+1]$对所有$i \in [1,n]$都成立时答案是YES，否则答案就是NO。

复杂度分析

时间复杂度

对于每个$case$，只遍历了一遍数组就求出了答案，因此算法的时间复杂度为$O(n)$。

空间复杂度

除了输入的$a$和$b$两个数组，只使用了有限几个变量，因此算法的额外空间复杂度为$O(1)$。

C++ 代码

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

using namespace std;
const int N = 200010;
int T, n, a[N], b[N];

bool solve() {
    for(int i = 1; i <= n; i++) {
        if(a[i] < b[i]) {
            // a[i]要变成b[i]，说明a[i+1]至少要为b[i]-1
            if(i < n) {
                if(b[i] - 1 > b[i + 1]) return false;
            }else {
                if(b[i] - 1 > b[1]) return false;
            }
        }else if(a[i] > b[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
        }
        if(solve()) {
            puts("YES");
        }else {
            puts("NO");
        }
    }
    return 0;
}