CF1690B Array Decrements

Coros_Trusds · 2022-06-08 06:33:52 · 题解

题目分析

• 如果 \exists i,b[i]\gt a[i]，那么无解。

• 如果所有的 a[i]-b[i] 都相等，那么有解。

• 否则，找出 t=\max\{a[i]-b[i]\}，如果 a[i]-b[i]\neq t，那有可能 a[i] 提前停下了，标志就是 b[i]=0。所以如果 \exists i,a[i]-b[i]\neq t,b[i]\neq 0，那么无解。否则有解。

代码

// Problem: B. Array Decrements
// Contest: Codeforces - Codeforces Round #797 (Div. 3)
// URL: https://codeforces.com/contest/1690/problem/B?f0a28=1
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date:2022-06-07 22:55
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <cstring>//need "memset"
#include <numeric>
#include <algorithm>
#include <cmath>
#define enter putchar(10)
#define debug(c,que) std::cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) std::cout << arr[i] << w;
#define speed_up() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define stop return(0)
const int mod = 1e9 + 7;
inline int MOD(int x) {
    if(x < 0) x += mod;
    return x % mod;
}
namespace Newstd {
    inline int read() {
        int ret = 0,f = 0;char ch = getchar();
        while (!isdigit(ch)) {
            if(ch == '-') f = 1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            ret = (ret << 3) + (ret << 1) + ch - 48;
            ch = getchar();
        }
        return f ? -ret : ret;
    }
    inline double double_read() {
        long long ret = 0,w = 1,aft = 0,dot = 0,num = 0;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') w = -1;
            ch = getchar();
        }
        while (isdigit(ch) || ch == '.') {
            if (ch == '.') {
                dot = 1;
            } else if (dot == 0) {
                ret = (ret << 3) + (ret << 1) + ch - 48;
            } else {
                aft = (aft << 3) + (aft << 1) + ch - '0';
                num ++;
            }
            ch = getchar();
        }
        return (pow(0.1,num) * aft + ret) * w;
    }
    inline void write(int x) {
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace Newstd;

const int N = 5e4 + 5;
int a[N],b[N];
int T,n;
inline void solve() {
    n = read();
    for (register int i = 1;i <= n; ++ i) a[i] = read();
    for (register int i = 1;i <= n; ++ i) b[i] = read();
    for (register int i = 1;i <= n; ++ i) {
        if (b[i] > a[i]) {
            puts("NO");
            return;
        }
    }
    int Max = 0;
    bool mark = true;
    for (register int i = 1;i <= n; ++ i) {
        Max = std::max(Max,a[i] - b[i]);
    }
    for (register int i = 1;i <= n; ++ i) {
        if (Max != a[i] - b[i]) {
            mark = false;
            break;
        }
    }
    if (mark) puts("YES");
    else {
        for (register int i = 1;i <= n; ++ i) {
            if (Max != a[i] - b[i] && b[i] != 0) {
                puts("NO");
                return;
            }
        }
        puts("YES");
    }
}
int main(void) {
    T = read();
    while (T --) {
        solve();
    }

    return 0;
}