IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 12届蓝桥杯省赛Java B组 双向排序 -> 正文阅读

[数据结构与算法]12届蓝桥杯省赛Java B组 双向排序

给定序列 (a1,a2,???,an)=(1,2,???,n),即 ai=i。

小蓝将对这个序列进行 m 次操作,每次可能是将 a1,a2,???,aqi 降序排列,或者将 aqi,aqi+1,???,an 升序排列。

请求出操作完成后的序列。

输入格式
输入的第一行包含两个整数 n,m,分别表示序列的长度和操作次数。

接下来 m 行描述对序列的操作,其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0 时,表示将 a1,a2,???,aqi 降序排列;当 pi=1 时,表示将 aqi,aqi+1,???,an 升序排列。

输出格式
输出一行,包含 n 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。

数据范围
对于 30% 的评测用例,n,m≤1000;
对于 60% 的评测用例,n,m≤5000;
对于所有评测用例,1≤n,m≤10^5,0≤pi≤1,1≤qi≤n。

import java.util.Scanner;
//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n,m;
		
		n=in.nextInt();m=in.nextInt();
		int[] a=new int[n+1];
		for(int i=1;i<=n;i++)a[i]=i;
		for(int i=0;i<m;i++) {
			int x,y;
			x=in.nextInt();y=in.nextInt();
			if(x==0) {
				down(a,1,y);
			}
			if(x==1) {
				up(a,y,n);
			}
		}
		for(int i=1;i<n+1;i++) {
			System.out.print(a[i]+" ");
		}
	}
	public static void up(int[] K,int s,int t) {
		int i,j;
		int temp;
		if(s<t){
			i=s;
			j=t+1;
			while(true){
			do{
				i++;
			}while(K[i]<K[s]&&i!=t);
			do{
				j--;
			}while(K[j]>K[s]&&j!=s);
			if(i<j){
				temp=K[i];
				K[i]=K[j];
				K[j]=temp;
			}
			else break;	
			}
			temp=K[s];
			K[s]=K[j];
			K[j]=temp;
			up(K,s,j-1);
			up(K,j+1,t);
		}
	}
	public static void down(int[] K,int s,int t) {
		int i,j,temp;
		if(s<t) {
			i=s;
			j=t+1;
			while(true) {
				do {
					j--;
				}while(K[j]<K[s]&&j!=s);
				do {
					i++;
				}while(K[i]>K[s]&&i!=t);
				if(i<j){
					temp=K[i];
					K[i]=K[j];
					K[j]=temp;
				}
				else break;	
			}
			temp=K[j];
			K[j]=K[s];
			K[s]=temp;
			down(K,s,j-1);
			down(K,j+1,t);
		}
	}
}

练习系统得分30,剩下超时,用的快速排序,想不通了,求一个满分算法···

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章           查看所有文章
加:2022-01-24 11:09:15  更:2022-01-24 11:12:42 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年7日历 -2024/7/19 15:05:56-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码