为什么只有第一个代码能够通过所有测试用例？

Question

我已经尝试了很多检查代码，但是找不到任何问题，所有代码都在进行二进制搜索以找到所需的位置，所以为什么只有第一个比最后两个更有效。第一个代码在4秒内解决了问题，而最后两个甚至在12秒后也无法解决。

问题：

您已给出一个具有元素的数组。现在对于给定的查询，您提供了一个整数，并且已经找到了最小总和，该总和是数组中所有值小于[]的元素的总和

。

输入格式：

第一行：整数

表示数组元素的数量。

第二行：

用空格分隔的整数表示数组元素。

第三行：整数

表示查询数量。

对于每个查询：新行包含一个整数。

输出格式：

对于每个查询，在新行中打印一个最小总和的整数。

作者：Suman Pramanik

语言：Java 8

第一密码：

import java.util.Arrays;

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

 

public class Main3 {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String nu = br.readLine();

        int n = Integer.parseInt(nu);

        String[] arregloS = new String[n];

        String aa = br.readLine();

        arregloS = aa.split(" ");

        int[] arreglo = new int[n];

        for (int i = 0; i<n ; i++) {

            arreglo[i] = Integer.parseInt(arregloS[i]);

        }

        Arrays.sort(arreglo);

        long[] arregloSumas = new long [n];

        for(int i = 0; i<n; i++) {

            if (i<=0) {

                arregloSumas[i]= arreglo[i];

            }else {

                arregloSumas[i]= arreglo[i]+ arregloSumas[i-1];

            }

        }

        String qu = br.readLine();

        int q = Integer.parseInt(qu);

        String query;
        int numQuery;

        for(int i =0 ; i<q; i++) {
            query = br.readLine();

            numQuery = Integer.parseInt(query);

            if(numQuery < arreglo[0]) {

                bw.write ("0\n");
            } else if (numQuery > arreglo[arreglo.length-1]) {
                bw.write (arregloSumas[arregloSumas.length-1]+"\n");
            } else {
                boolean find = false;

                int izq = 0;

                int der = arreglo.length-1;

                int pos = 0;

                while(izq<=der && !find){

                    int mid = (izq+der)/2;

                    if (arreglo[mid] >= numQuery) {
                        der = mid-1;
                    } else {
                        if(arreglo[mid+1] >= numQuery) {
                            pos = mid;
                            find = true;
                        } else {
                            izq = mid + 1;
                        }
                    }
                }

                bw.write (arregloSumas[pos]+"\n");
            }    
        }

        bw.close();
        br.close(); 
    }
}
第二个代码：

import java.util.*;

class TestClass {

public static void main(String args[] ) throws Exception 

{ 

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

long a[]=new long[n],sum=0;

for(int i=0;i<n;i++)

a[i]=sc.nextLong();

Arrays.sort(a);

long s[]=new long[n+1];

s[0]=a[0];

for(int i=1;i<n;i++)

s[i]=s[i-1]+a[i];

int q=sc.nextInt();

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

{

long m=sc.nextLong();

if(m<a[0])

System.out.println(0);

else if(m>a[n-1])

System.out.println(s[n-1]);

else

for(int j=n/2,h=n,l=0;;j=(h+l)/2)

{

if(a[j]<m && a[j+1]>=m)

{

System.out.println(s[j]);

break;

}

if(m<=a[j])

h=j;

else

l=j;

}

}

}

}
第3码。 ：

import java.util.*;

class TestClass {

public static void main(String args[] ) throws Exception 

{ 

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

long a[]=new long[n],sum=0;

for(int i=0;i<n;i++)

a[i]=sc.nextLong();

Arrays.sort(a);

long s[]=new long[n+1];

s[0]=a[0];

for(int i=1;i<n;i++)

s[i]=s[i-1]+a[i];

int q=sc.nextInt();

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

{

long m=sc.nextLong();

if(m<a[0])

System.out.println(0);

else if(m>a[n-1])

System.out.println(s[n-1]);

else

{

int k=Arrays.binarySearch(a,m);

if(k>=0)

System.out.println(s[k-1]);

else

System.out.println(s[k*-1-2]);

}

}

}

}

我已经尝试了很多检查代码，但是找不到任何问题，所有代码都在进行二进制搜索以找到所需的位置，所以为什么只有第一个比最后两个更有效。 ...

Answer 1

BufferedReader比Scanner快得多，因为它的缓冲区内存比Scanner大。您可以看到两个in this discussion之间的区别。