省建设厅网站6,江苏建设管理信息网站,民政局网站建设方案,创建网站的视频最小调整顺序次数、特异性双端队列
题目描述 有一个特异性的双端队列#xff0c;该队列可以从头部或尾部添加数据#xff0c;但是只能从头部移出数据。 小A依次执行2n个指令往队列中添加数据和移出数据。其中n个指令是添加数据#xff08;可能从头部添加、也可能从尾部添加…最小调整顺序次数、特异性双端队列
题目描述 有一个特异性的双端队列该队列可以从头部或尾部添加数据但是只能从头部移出数据。 小A依次执行2n个指令往队列中添加数据和移出数据。其中n个指令是添加数据可能从头部添加、也可能从尾部添加依次添加1到nn个指令是移出数据。 现在要求移除数据的顺序为1到n。 为了满足最后输出的要求小A可以在任何时候调整队列中数据的顺序。 请问 小A 最少需要调整几次才能够满足移除数据的顺序正好是1到n 输入描述 第一行一个数据n表示数据的范围。 接下来的2n行其中有n行为添加数据指令为 head add x 表示从头部添加数据 xtail add x 表示从尾部添加数据x 另外 n 行为移出数据指令指令为remove 的形式表示移出1个数据 1 ≤ n ≤ 3 * 10^5。 所有的数据均合法。 输出描述 一个整数表示 小A 要调整的最小次数。 源码和解析 解析 其实这个题只要理解了就其实还蛮简单的。小编当时做这个提题目时候前面一脸懵B压根不知道在说个啥。就只知道要调整次数但是不确定这个调整次数是啥。 head add 1 [1] tail add 2 [1, 2] remove [2] head add 3 [3, 2] tail add 4 [3, 2, 4] head add 5 [5, 3, 2, 4] remove 排序了 [3, 4, 5] remove [4, 5] remove [5] remove [] 这个是用例中的例子 输出过程。 认真去体会每个指令执行后的结果 若输入变成 5 head add 2 tail add 1 remove head add 3 tail add 4 head add 5 remove remove remove remove 排序了1次 那么其输出过程为 head add 2 [2] tail add 1 [2, 1] remove 排序了 [2] head add 3 [3, 2] tail add 4 [3, 2, 4] head add 5 [5, 3, 2, 4] remove 排序了 [3, 4, 5] remove [4, 5] remove [5] remove [] 排序了2次 》可以推出 当集合中首位值不是集合中最小值是需要进行调整。而一次调整包含了多次交换位置过程。可以简单的理解为1次排序过程。 示例代码
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;public class T33 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);String input scanner.nextLine();int num Integer.parseInt(input); // 数据范围 并非是数的个数ListInteger numList new ArrayListInteger();int count 0;// 调整次数int removeNum 1;// 下一次需要移走哪一个for (int i 0; i num * 2; i) {input scanner.nextLine();String strArr[] input.split( );System.out.println(input);if (strArr[0].equals(remove)) {// remove 从头部移出数据if (numList.get(0) removeNum) {numList.remove(0);removeNum;} else {count;// 调整次序 从小到大排序一下numList.sort(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {if (o1 o2)return 1;if (o1 o2)return -1;return 0;}});System.out.println(排序了);numList.remove(0);removeNum;}}// 头部添加if (strArr[0].equals(head)) {numList.add(0, Integer.parseInt(strArr[2]));// continue;} else if (strArr[0].equals(tail)) {// 尾部添加numList.add(Integer.parseInt(strArr[2]));}System.out.println(numList);}System.out.println(count);}
}
