【蓝桥杯】历届真题 双向排序（省赛）Java
【问题描述】
给定序列(ai,a2,…… ,an)= (1,2,. ,n)，即ai = i。
小蓝将对这个序列进行m次操作，每次可能是将ai,a2,… · ,aq。降序排列，或者将aq;,aq+1,…. ,an升序排列。
请求出操作完成后的序列。
【输入格式】
输入的第一行包含两个整数n, m，分别表示序列的长度和操作次数。
接下来m行描述对序列的操作，其中第i行包含两个整数p;,q表示操作类型和参数。当pi=0时，表示将ai,ag,… ,aq降序排列；当pi=1时，表示将aq;, aq;+1,… ,an升序排列。
【输出格式】
输出一行，包含n个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。
【样例输入】
3 3
0 3
1 2
0 2
【样例输出】
3 1 2
【样例说明】
原数列为(1,2,3)。
第1步后为(3,2,1)。
第⒉步后为(3,1,2)。
第3步后为(3,1,2)。与第2步操作后相同，因为前两个数已经是降序了。
【评测用例规模与约定】
对于30%的评测用例，n,m ≤ 1000；
对于60%的评测用例，n,m ≤ 5000；
对于所有评测用例，1≤n,m ≤ 100000，0≤pi≤1，1≤ qi ≤ n。
【思路与分析】
这道题初看很容易出思路，无非是调用sort方法进行排序，若是逆向就写一个比较器就完了。但当你费劲心思写出来自认为十分优化的代码信心满满地提交之后，问题就来了。要么超时，要么超内存，让人很是费解。
此时，你再次将目光放到了题目中，发现了一个忽视了的可以极大优化的点，同样是制胜点：操作数分有效操作和无效操作！若你能够意识到这一点，那么这道题就已经通过一半了。
首先，相同的操作间可以相互忽略，同样的操作，你只需要选择一个操作区间最大的操作即可。同样，操作区间相同，不同的操作也可以相互忽略！无非是倒过来再颠过去，若一个一个地执行，那可是大大地浪费了性能和宝贵的时间。
还是那句话，如果你有一个清晰的思路，写代码就是砍瓜切菜。
来吧，展示。
【代码：满分】
import java.util.*;
class Main{
public static class arr{
int x=0;
int y=0;
arr(int a,int b) {
x=a;
y=b;
}
}
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
arr[] arr= new arr[n+1];
int top=0;
int num[]=new int[n+1];
int p,q; //代表ap,aq
for(int i=0;i<m;i++) {//记录有效操作步骤
p=sc.nextInt();
q=sc.nextInt();
if(p==1&&top>0) {//top大于0是为了保证第一次操作为0操作,操作1为无效操作
while(top>0&&arr[top].x==1) {//top记录上一个操作
//取范围最大的连续操作
if(arr[top].y<=q)
q=arr[top].y;
--top;//将上一个操作的q赋值给当前的q，并将top移动至上一个操作的上一步
}
//若相邻的相同操作的范围小于当前范围，top更新，舍弃小范围
while(top>=2&&arr[top-1].y>=q) {
top-=2;//删除2个操作数（一组0 1操作）
}
arr[++top]=new arr(1,q);//top始终停留在要记录操作的前一步
}
if(p==0){
while(top>0&&arr[top].x==0) {
if(arr[top].y>=q)
q=arr[top].y;
--top;
}
while(top>=2&&arr[top-1].y<=q){//若不加=，会存两次相同的值（边界问题）
top-=2;
}
arr[++top]=new arr(0,q);
}
}
int k=n;
int l=1,r=n; //l：左下标、r右下标 以判断是否跳过或执行操作
for(int i=1;i<=top;i++) {
if(arr[i].x==0) {
while(l<=r&&arr[i].y<r)
num[r--]=k--;
}
if(arr[i].x==1) {
while(l<=r&&arr[i].y>l)
num[l++]=k--;
}
}
if(top%2==0) {//操作1
while(l<=r)
num[r--]=k--;
}
else {//操作0
while(l<=r)
num[l++]=k--;
}
for(int i=1;i<=n;i++) {
System.out.print(num[i]+" ");
}
}
}【总结】
该题思维量适中，对编程能力的考察仍是占了大头，需要有清晰的思路与编程经验才能在数组边界等问题上轻松应对。同时，告诉我们一定一定要认真审题，细细思考，才能不错过每一个该答对的题，每一分该拿的分。
本篇博客到此就结束了，如果有帮到你，我很开心。
下面po出我第一次提交的代码，当做教训，警醒自己。
【代码：暴力（未通过）】
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //序列长度
int m = sc.nextInt(); //操作次数
int[] caoZuo = new int[m*2]; //存储操作数
//将操作数录入存储数组
for(int i=0; i<caoZuo.length; i++){
caoZuo[i] = sc.nextInt();
}
//新建元素数组
Integer[] a = new Integer[n];
//若元素为1，直接return 节约时间
a[0] = 1;
if(n==1){
System.out.println(a[0]);
return;
}
//为需要排序的数组填充值
for(int i=1; i<a.length; i++){
a[i] = 1+i;
}
//i:操作类型 j:参数
for(int i=0; i<caoZuo.length-1; i+=2){
for(int j=1; j<caoZuo.length; j+=2){
//逆序排序
if(caoZuo[i] == 0){
Arrays.sort(a, 0, caoZuo[j], new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return b-a;
}
});
//正向排序
} else if(caoZuo[i] == 1){
Arrays.sort(a, caoZuo[j], a.length-1);
}
}
}
for(int i=0; i<a.length; i++){
if(i != a.length-1){
System.out.print("" + a[i] + " ");
} else {
System.out.print("" + a[i]);
}
}
}
}