java - 玩数字编程挑战(在java中查找子数组的平均值)

Question

我正在尝试解决这个数字游戏。我已经通过了测试用例，但是我不断超出时间限制。有人可以帮助我提高其性能以通过时间限制吗？

问题:

给你一个包含 n 个数字和 q 个查询的数组。对于每个查询，您必须打印从 L 到 R 的子数组的期望值(平均值)的下限。

输入:

第一行包含两个整数N和Q，分别表示数组元素的数量和查询的数量。

下一行包含 N 个空格分隔的整数，表示数组元素。

接下来的 Q 行包含两个整数 L 和 R(数组的索引)。

输出:

打印一个表示答案的整数。

限制:

1<= N、Q、L、R <= 10^6

1<= 数组元素 <= 10^9

我的代码:

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

class TestClass 
{
    public static void main(String args[] ) throws IOException 
    {
       Scanner sc=new Scanner(System.in);
       int n= sc.nextInt();
       int q= sc.nextInt();
       int arr[]=new int[n];
       int sums[]=new int[n+1];
       sums[0]=0;
       for(int i=0;i<n;i++)
       {
           arr[i]=sc.nextInt();
           sums[i+1]=sums[i]+arr[i];

       }
       for(int i=0;i<q;i++)
       {

           int q1=sc.nextInt();
           int q2=sc.nextInt();
           int end=(q2-q1)+1;
           int mean= (sums[q2]-sums[q1-1])/end;
           System.out.println(mean);
       }
    }
}

Answer 1

根据我不太科学的测试，这会使速度加倍:

    sc.nextLine(); // to finish row #1
    String line = sc.nextLine();
    String[] parts = line.split(" ");
    for (int i = 0; i < parts.length; i++) {
        arr[i] = Integer.parseInt(parts[i]);
        sums[i + 1] = sums[i] + arr[i];
    }

如您所见，小技巧是最大限度地减少扫描仪必须读取的次数(因为每次“读取”周围通常都会有一些“滞后”)。我是从文件中读取的，而不是从 System.in 中读取的，所以也许您在设置中不会看到相同的改进。