用的是JAVA8,代码如下 题目里给的输入输出样例得到的正确答案,但是用时900+ms了
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static long abs(long x) {
if (x >= 0) return x;
else return -x;
}
public static long calculate(int n, long k, long x, long y, long[] xMod, long[] yMod) {
//1、判失败部分。
long xSum = 0;
long ySum = 0;
for (int i = 0; i < n; i++) {
xSum += xMod[i];
ySum += yMod[i];
}
long sum = xSum + ySum;
if (sum >= k * n && (xSum * x < 0) && (ySum * y < 0)) {
//如何判失败?如果目的地与季风方向相反(完全逆风而不是单向逆风,单向逆风的话总能苟到终点),
//且一个周期总步数无法抵御季风影响。则不可能到达。
// (换言之,如果一个周期内在x或y方向上做不到靠近目的地,则不可能到达)
return -1;
}
//2、判成功部分
long xNow = 0;
long yNow = 0;//当前坐标
int m = 0;
while (xNow != x && yNow != y) {//当到达目的地时结束循环。
m++;//+1天。
xNow += xMod[(m - 1) % n];
yNow += yMod[(m - 1) % n];//累计到当日,季风的总影响。
if ((abs(x - xNow) + abs(y - yNow)) <= m * k) {
//如果说目前累计可行走步数,大于等于季风影响下当前位置到目的地的曼哈顿距离,则当日可到达。
return m;
}
}
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int terms = sc.nextInt();//测试样例个数
int[] n = new int[terms];//季风的一个周期
long[] k = new long[terms];//每天的步数限制(判定失败条件:一个周期内总步数小于一个周期内的季风数值总和。则返回-1)
long[] x = new long[terms];//目的地x坐标
long[] y = new long[terms];//目的地y坐标
Deque<Long> wind = new LinkedList<>();//暂时保存季风信息的队列。
for (int i = 0; i < terms; i++) {
//基本数据,包括:季风周期,每天步数限制,目的地x坐标,目的地y坐标
n[i] = sc.nextInt();
k[i] = sc.nextInt();
x[i] = sc.nextInt();
y[i] = sc.nextInt();
//暂时用队列保存季风数据。
for (int p = 0; p < 2 * n[i]; p++) {
wind.offer((long) sc.nextInt());
}
}
long time=System.currentTimeMillis();
//输入结束。
//开始测试每组样例。
for (int now = 0; now < terms; now++) {
long[] xMod = new long[n[now]];
long[] yMod = new long[n[now]];
for (int i = 0; i < n[now]; i++) {
xMod[i] = wind.poll();
yMod[i] = wind.poll();
}//录入该样例的季风数据。
System.out.println(calculate(n[now], k[now], x[now], y[now], xMod, yMod));
}
}
}