import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while (T-- > 0) {
int n = in.nextInt();
long sum = 0;
int max = 0;
while (n-- > 0) {
int a = in.nextInt();
sum += a;
if (a > max) max = a;
}
long x = in.nextInt();
long y = in.nextInt();
long p = in.nextInt();
long q = in.nextInt();
long movex = (p - x);
long movey = (q - y);
long move = ((movex > 0) ? movex : -movex) + ((movey > 0) ? movey : -movey);
if ((sum % 2 == move % 2) && (sum >= move) && ((max * 2 - sum) <= move)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
这一题，如果看题面直接想要去做暴力搜索那就走弯路了
题目中的描述：对于第 i 次移动，她都需要选择这样两个整数 l 和 r，满足∣l∣+∣r∣= ai，随后移动到 (x+l,y+r) 这个位置。
实际上，就是第 i 次移动到距离上一个位置曼哈顿距离为ai的位置。
不妨认为第i次移动是将点从(xi,yi)移动到了(x(i+1),y(i+1))
连续的两次移动ai、a(i+1)，如果在两个方向上总共抵消了2k步（显然，抵消的只会有偶数步），那么，点经过两次移动从(xi,yi)抵达(x(i+2),y(i+2))，两点的曼哈顿距离是ai+a(i+1)-2k，0<=k<=MIN{ai,a(i+1)}
那么，对于所有的n次移动，最后可以抵达的位置距离起点的曼哈顿距离为 SUM{ai} - 2K，2K为总共的被抵消的步数。
2K最小可以为0，也就是每一次移动都往同一个方向走，
2K最大不超过SUM{ai}，
当存在aj>SUM{ai}/2时，K<=SUM{ai}-aj，也就是最长的一次移动步数超过总步数的一半时，抵消最多的情况是其余的移动全部用来与它抵消。
而不存在这样的aj时，总可以找到一种方法使得2K取到最接近SUM{ai}的值，
然后，K可以在最大和最小值直接任取。
这样，依次计算SUM{ai}、max_dist = SUM{ai}、Kmax = MIN{SUM{ai} - MAX{ai} , SUM{ai}/2}、min_dist = SUM{ai} - 2*Kmax
再计算target_dist = |p - x| + |q - y|
只要target_dist与SUM{ai}有相同奇偶性，且 min_dist<=target_dist<=max_dist 即认为目标点(p,q)可到达
红字的部分单独标出来，是因为虽然严格意义上，解题应当考虑这一部分，但我做题的时候，平台给这一题的测试用例没有考虑这部分内容，做与不做均不影响通过
以下是一个用于红字部分的测试用例：
测试输入： 2 1 6 1 1 3 3 3 2 2 6 0 0 0 0 预期输出： NO NO
注：
曼哈顿距离：
常见的距离定义 sqrt{(x0-x1)^2+(y0-y1)^2}被称为欧几里得距离，是平面上两点间最短路径的长度。
曼哈顿距离定义为|x0-x1|+|y0-y1|，是平面上两点间限定了点的移动只能沿坐标轴方向的前提下的最短路径长。
京公网安备 11010502036488号