题目解析
判断给定顺序 是否能排成 1~n
解题思路
栈的应用
每次判断当前的元素是否为当前填充到的色号
如果是 那么就将色号+1
否则就存入栈中
每次判断完后去看栈中的是否为接下来的色号
最后判断栈中有无元素
有就是不能排列
否则就是能排列
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e3;
static int shu[] = new int[N + 10];
static int n, m;
static boolean is()
{
// 填装到哪一种色号的球了
int pos = 1;
Stack<Integer> st = new Stack<Integer>();
for (int i = 1; i <= n; i++)
{
if (shu[i] != pos)
st.add(shu[i]);
else
pos++;
if (st.size() > m)
return false;
while (st.size() != 0 && st.peek() == pos)
{
pos++;
st.pop();
}
}
while (st.size() != 0 && st.peek() == pos)
{
pos++;
st.pop();
}
return pos == n + 1;
}
public static void main(String[] args)
{
n = sc.nextInt();
m = sc.nextInt();
int k = sc.nextInt();
while (k-- > 0)
{
for (int i = 1; i <= n; i++)
shu[i] = sc.nextInt();
if (is())
out.println("YES");
else
out.println("NO");
}
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}