【蓝桥杯】双向排序（省赛）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 ≤ 1000000≤pi≤11≤ 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]);
			}
		}
	}
}