行走

[题目链接](https://www.nowcoder.com/practice/9c9835bf3c9c4947bce69e30d4412217)

思路

小美在二维坐标平面上，从 $(sx, sy)$ 出发，进行 $n$ 次移动。第 $i$ 次移动选择满足 $|dx| + |dy| = a_i$ 的整数 $dx, dy$ ，移动到 $(x + dx, y + dy)$ 。问能否恰好到达 $(ex, ey)$ 。

三个关键条件

设目标曼哈顿距离 $d = |ex - sx| + |ey - sy|$ ，总步长和 $S = \sum a_i$ ，最大步长 $M = \max(a_i)$ 。

条件一：总步长足够。 显然需要 $S \geq d$ ，否则无论怎么走都到不了。

条件二：奇偶性匹配。 每步移动 $a_i$ 的曼哈顿距离，净位移的曼哈顿距离与 $S$ 同奇偶（多走的部分必须以"往返"形式抵消，每次抵消消耗 2 的距离）。因此需要 $(S - d) \bmod 2 = 0$ 。

条件三：最大步长不能过大。 如果某一步 $a_i$ 特别大，剩余所有步的总长 $R = S - M$ 也无法"拉回来"。具体地， $n$ 步的可达范围要求净位移至少为 $M - R$ （最大步迈出去，其余步全力往回拉，也只能抵消 $R$ 的距离）。因此需要 $d \geq M - R$ ，即 $d + R \geq M$ 。

可以直觉理解：将最大步固定方向走出去，剩余 $n - 1$ 步的总长为 $R$ ，它们可以自由调整方向。如果 $R \geq M$ ，那么剩余步本身就能完全抵消最大步，条件三自动满足。否则至少还有 $M - R$ 的"欠债"需要目标距离 $d$ 来"消化"。

三个条件为何充分

当这三个条件同时满足时，我们总能构造一种合法方案。核心思路是：先用两步"消耗"掉多余的距离 $S - d$ ，再让剩余的步沿着目标方向走。在二维平面中，两步 $a_i, a_j$ 可以通过在 $x, y$ 方向上灵活分配，实现范围 $[|a_i - a_j|, a_i + a_j]$ 内任意同奇偶曼哈顿距离的净位移。因此只要总量和奇偶都对，就一定有解。

样例演示

样例 1： $n=2, a=[0,0]$ ，起点 $(1,1)$ ，终点 $(1,1)$ 。 $d=0, S=0, M=0, R=0$ 。三个条件全满足，输出 YES。

样例 2： $n=3, a=[1,1,1]$ ，起点 $(1,1)$ ，终点 $(2,2)$ 。 $d=2, S=3, M=1, R=2$ 。条件一 $3 \geq 2$ 满足；条件三 $2 \geq 1-2=-1$ 满足；但条件二 $(3-2)=1$ 为奇数，不满足。输出 NO。

复杂度分析

时间复杂度： $O(n)$ ，遍历数组求和与最大值。
空间复杂度： $O(1)$ ，只需常数额外空间。

代码

C++
Java

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

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        long long S = 0, mx = 0;
        for(int i = 0; i < n; i++){
            long long a;
            scanf("%lld", &a);
            S += a;
            mx = max(mx, a);
        }
        long long sx, sy, ex, ey;
        scanf("%lld%lld%lld%lld", &sx, &sy, &ex, &ey);
        long long d = abs(ex - sx) + abs(ey - sy);
        long long R = S - mx;
        if(d <= S && (S - d) % 2 == 0 && d >= mx - R){
            puts("YES");
        } else {
            puts("NO");
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            long S = 0, mx = 0;
            for (int i = 0; i < n; i++) {
                long a = Long.parseLong(st.nextToken());
                S += a;
                mx = Math.max(mx, a);
            }
            st = new StringTokenizer(br.readLine().trim());
            long sx = Long.parseLong(st.nextToken());
            long sy = Long.parseLong(st.nextToken());
            long ex = Long.parseLong(st.nextToken());
            long ey = Long.parseLong(st.nextToken());
            long d = Math.abs(ex - sx) + Math.abs(ey - sy);
            long R = S - mx;
            if (d <= S && (S - d) % 2 == 0 && d >= mx - R) {
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }
        }
        System.out.print(sb);
    }
}