为什么会被MLE啊,第一次玩洛谷,真看不懂

P2249 【深基13.例1】查找

ONELINE @ 2023-02-20 16:53:34


import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
 InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int n = in.nextInt();
int T = in.nextInt();
int[] num = new int[n];
for(int i = 0;i < n;i ++) num[i] = in.nextInt();
while(T-- > 0)
{
    int k = in.nextInt();
    int l = 0;
    int r = n-1;
    int f = 0;
    while(l < r)
    {
        int mid = l - ( l - r) /2;
        if(num[mid] >= k) r = mid;
        else l = mid + 1;

    }
    if(num[l] == k)
        out.print(l+1+" ");
    else
        out.print(-1+" ");
}

    out.flush();

}
}

class InputReader {
    private final BufferedReader buf;
    private StringTokenizer tkl;

    public InputReader(InputStream is) {
        buf = new BufferedReader(new InputStreamReader(is));
    }

    public boolean hasNext() {
        try {
            while (tkl == null || !tkl.hasMoreElements()) tkl = new StringTokenizer(buf.readLine());
        } catch (Exception e) {
            return false;
        }
        return true;
    }

    public String next() {
        return hasNext() ? tkl.nextToken() : null;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}

by FishWangX @ 2023-02-20 16:58:27

一般是讨论解题思路吧?不确定是否可以直接贴上代码。


by ud2_ @ 2023-02-20 17:20:13

MLE 说明对象太多。StringTokenizer 不仅把整个输入串放在内存里,还会产生大量的新 String 存放子串,而 StreamTokenizer 不会。算法题中只需要解析整数时可以用这样的方式输入:

class TokenizingReader {
  private final StreamTokenizer st;

  public TokenizingReader(Reader r) {
    this.st = new StreamTokenizer(r);
  }

  public int nextInt() throws IOException {
    this.st.nextToken();
    return (int) this.st.nval;
  }
}

by ONELINE @ 2023-02-20 19:56:51

@ud2_ 感谢,java输入太慢了,一直用的都是这个快读板子,第一次在这里出现了问题


by ONELINE @ 2023-02-20 19:58:11

@yuyooo 我自信的觉得代码是没问题的,但就是有什么不是算法方面的问题


by FishWangX @ 2023-02-20 21:54:52

@ONELINE 明白,是啊,常见现象。加油,可能还是不够熟练。


|