xiaoqi666 @ 2023-01-12 13:57:52
对java不熟悉，求大佬解决一下。-。-
java代码（80分）：2和10测试点MLE 记录
import java.io.*;
public class Main {
static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static PrintWriter cout = new PrintWriter(bw);
static StreamTokenizer st = new StreamTokenizer(buf);
public static int nextInt() throws IOException {
st.nextToken();
return (int)st.nval;
}
public static long nextLong() throws IOException {
st.nextToken();
return (long)st.nval;
}
static int q[] = new int[1000010];
static int a[] = new int[1000010];
public static void main(String[] args) throws IOException {
int n,k;
n = nextInt();
k = nextInt();
for(int i = 0;i < n;i ++) a[i] = nextInt();
int hh = 0,tt = -1;
for(int i = 0;i < n;i ++)
{
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++ tt] = i;
if(i >= k - 1) cout.print(a[q[hh]] + " ");
}
hh = 0; tt = -1;
cout.println();
for(int i = 0;i < n;i ++)
{
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++ tt] = i;
if(i >= k - 1) cout.print(a[q[hh]] + " ");
}
cout.flush();
}
}
一模一样的C++代码（100分）：
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N],q[N];
int main()
{
int n,k;
cin >> n >> k;
for(int i = 0;i < n;i ++) cin >> a[i];
int hh = 0,tt = -1;
for(int i = 0;i < n;i ++)
{
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] >= a[i]) tt --;
q[ ++tt ] = i ;
if(i >= k -1) cout << a[q[hh]] << " ";
}
cout << endl;
hh = 0,tt = -1;
for(int i = 0;i < n;i ++)
{
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && a[q[tt]] <= a[i]) tt --;
q[ ++tt ] = i ;
if(i >= k -1) cout << a[q[hh]] << " ";
}
return 0;
} by KKKZOZ @ 2023-01-12 14:45:44
咋又遇到你了哈哈
这题内存对于Java来说比较紧，所以你单独给q开个这么大的数组就MLE了（Java嘛，跑得慢一点，开销大一点，很正常的）
可以把那个q数组变成一个LinkedList或者ArrayDeque都能过
其实你写Java发现过不了的话，你可以去那道题的提交界面筛选Java语言，看看别人的Java代码是咋过的
by xiaoqi666 @ 2023-01-12 16:53:28
@KKKZOZ 哈哈哈，好巧啊。
我以前用C++的，最近才开始用java，这不是不熟练嘛。（其实就是菜哈哈哈）
还得多谢你的java快读模板哈哈哈
by YuchaoM @ 2023-02-02 16:39:32
@KKKZOZ 题解哪里好像没有筛选语言的功能，请问怎么找
by KKKZOZ @ 2023-02-02 22:44:07
@YuchaoM 去提交记录里面找
by YuchaoM @ 2023-02-03 15:17:29
@KKKZOZ 哦哦，提交记录里筛选出语言和通过的，但是点进去，查看不了别人提交的代码。洛谷的题目不会写，没有答案参考很烦哦，请问你是怎么刷的
by KKKZOZ @ 2023-02-03 15:59:17
@YuchaoM 洛谷有个代码公开计划，默认好像是参加的，你在这道题上拿了60分及以上，才能看别人的代码
不会写的话，你可以看题解撒，虽然题解都是用C/C++写的，但是在算法题这一块，Java和他俩的写法基本是相同的，C++的STL你可以用Java.util.* 包里的东西来替代，思路看懂了的话，代码还是很好写的
如果你非要看一道你不会的题的Java的代码，你就去题解区复制一篇C++的题解（能过的那种），随便改几个变量什么的（防止系统认定你抄袭），得了100分再去看提交记录里的Java代码就行了
by YuchaoM @ 2023-02-03 16:26:29
@KKKZOZ 好哦，大佬能帮忙看看 P1440 求m区间内的最小值，这道题，我的代码为什么没过吗。一个MLE,4个TLE
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n + 1];
Deque<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(0);
for (int i = 1; i < n; i++) {
while (!q.isEmpty() && arr[q.peekLast()] >= arr[i]) {
q.pollLast();
}
q.offerLast(i);
//如果队头元素不属于前m个，删头
if (!q.isEmpty() && q.peekFirst() <= i - m) {
q.pollFirst();
}
System.out.println(arr[q.peekFirst()]);
}
scanner.close();
}
}还有我看了一下别人的代码，好多都不是直接用Scanner 进行输入的，都是自己封装一个，为什么？
by KKKZOZ @ 2023-02-03 16:34:21
@YuchaoM 因为Scanner的读入速度和System.out的写出速度太慢了，你这道题就是这个原因
TLE就是时间超了，套个快读模板就能过了(MLE好像也是和Scanner有关)
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class Main {
static int status;
static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static PrintWriter cout = new PrintWriter(bw);
static StreamTokenizer st = new StreamTokenizer(buf);
public static int nextInt() throws IOException {
status = st.nextToken();
return (int) st.nval;
}
public static long nextLong() throws IOException {
status = st.nextToken();
return (long) st.nval;
}
public static String nextString() throws IOException {
status = st.nextToken();
return st.sval;
}
public static void main(String[] args) throws IOException {
int n = nextInt();
int m = nextInt();
int[] arr = new int[n + 1];
Deque<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) {
arr[i] = nextInt();
}
System.out.println(0);
for (int i = 1; i < n; i++) {
while (!q.isEmpty() && arr[q.peekLast()] >= arr[i]) {
q.pollLast();
}
q.offerLast(i);
//如果队头元素不属于前m个，删头
if (!q.isEmpty() && q.peekFirst() <= i - m) {
q.pollFirst();
}
cout.println(arr[q.peekFirst()]);
}
cout.flush();
}// End of main
}by YuchaoM @ 2023-02-03 17:25:37
@KKKZOZ 牛蛙牛蛙，这个模板真好用，谢谢你哦
by YuchaoM @ 2023-02-04 16:20:54
@KKKZOZ 今天发现了一个问题这个模板不能把10001011这样的序列读入为字符串
static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StringTokenizer in;
// 在没有其他输入时返回 null
static String next() {
try {
while (in == null || !in.hasMoreTokens())
in = new StringTokenizer(r.readLine());
return in.nextToken();
} catch (Exception e) {
}
return null;
}
static int nextInt() {
return Integer.parseInt(next());
}
static double nextDouble() {
return Double.parseDouble(next());
}
static long nextLong() {
return Long.parseLong(next());
}这个模板可以