用KEGG网站做通路富集分析,node.js企业网站开发,制作网站空间域名,登封建设局网站试题 I: 双向排序 本题总分#xff1a;25 分
【问题描述】 给定序列 (a1, a2, , an) (1, 2, , n)#xff0c;即 ai i。 小蓝将对这个序列进行 m 次操作#xff0c;每次可能是将 a1, a2, , aqi 降序排列#xff0c; 或者将 aqi , aqi1, , an 升序排列。 请求…试题 I: 双向排序 本题总分25 分
【问题描述】 给定序列 (a1, a2, · · · , an) (1, 2, · · · , n)即 ai i。 小蓝将对这个序列进行 m 次操作每次可能是将 a1, a2, · · · , aqi 降序排列 或者将 aqi , aqi1, · · · , an 升序排列。 请求出操作完成后的序列。
【输入格式】 输入的第一行包含两个整数 n, m分别表示序列的长度和操作次数。 接下来 m 行描述对序列的操作其中第 i 行包含两个整数 pi, qi 表示操作 类型和参数。当 pi 0 时表示将 a1, a2, · · · , aqi 降序排列当 pi 1 时表示 将 aqi , aqi1, · · · , an 升序排列。
【输出格式】 输出一行包含 n 个整数相邻的整数之间使用一个空格分隔表示操作 完成后的序列。
【样例输入】 3 3 0 3 1 2 0 2
【样例输出】 3 1 2
【样例说明】 原数列为 (1, 2, 3)。 第 1 步后为 (3, 2, 1)。 第 2 步后为 (3, 1, 2)。 第 3 步后为 (3, 1, 2)。 与第 2 步操作后相同因为前两个数已经是降序了。
【评测用例规模与约定】 对于 30% 的评测用例n, m ≤ 1000 对于 60% 的评测用例n, m ≤ 5000 对于所有评测用例1 ≤ n, m ≤ 1000000 ≤ pi ≤ 11 ≤ qi ≤ n。 60分通过6/10测评点其余测评点超时Java代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);ComparatorInteger comparator new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1; //降序排序}};int n scanner.nextInt();int m scanner.nextInt();Integer[] num new Integer[n];for (int i 0; i num.length; i) {num[i] i 1;}for (int i 0; i m; i) {int p scanner.nextInt();int q scanner.nextInt();if (p 0) {Arrays.sort(num, 0, q, comparator);}else {Arrays.sort(num, q-1, num.length);}}for (Integer integer : num) {System.out.print(integer );}}
}满分Java代码 参考博客
import java.util.Scanner;public class Main {static class pair { int x, y;public pair(int x, int y) {super();this.x x;this.y y;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();pair[] pairs new pair[n1];int top0;for(int i0;im;i) { //记录有效步骤int p scanner.nextInt();int q scanner.nextInt();if(p 1 top 0) {while(top 0 pairs[top].x 1) {//连续出现相同的操作if(pairs[top].yq) qpairs[top].y;top--;}//相邻的相同操作的范围小于当前范围while(top 2 pairs[top-1].y q) {top - 2;}pairs[top] new pair(1,q);}if(p0){while(top 0 pairs[top].x 0) {if(pairs[top].y q) qpairs[top].y;top--;}while(top 2 pairs[top-1].y q) top - 2;pairs[top] new pair(0,q); }}int num[] new int[n1];int k n;int l 1,r n;for(int i 1; i top; i) {if(pairs[i].x 0) {while(l r pairs[i].y r)num[r--] k--;}if(pairs[i].x 1) {while(l r pairs[i].y l)num[l] k--;}}if(top % 2 0) {//为操作1while(l r)num[r--] k--;}else {//为操作0while(l r)num[l] k--;}for(int i 1; i n; i) {System.out.print(num[i] );}}
}
