好像时间复杂度已经是O(n)了,但还是超时
查看原帖
好像时间复杂度已经是O(n)了,但还是超时
1342133
shuihuota楼主2024/4/16 01:50

用的是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));

        }

    }
}

2024/4/16 01:50
加载中...