Question

pascal题目

Alice勤工俭学做纪中的图书管理员，学校让他管理一个小的图书室，里面有N本书，放书的地方是一个非常狭窄的书柜，以至于只能把一本书放在另一本书的上面，现在Alice要做的工作是把书按照编号排序。 Alice能轻易地把一本书从书柜里拔出来，但放到一堆书中去非常困难，所以只能把拔出来的书放到最上面，所以排序的唯一方法就是不停地拔出一本书再放到最上方。 给出N本书从上到下的编号，N本书用1到N编号，每本书的编号各不相同，要求Alice用最少的操作次数使得书柜中的书从上到下依次为1，2，…,N。例如N=3，一开始为(3,2,1)，两次移动就可以完成，第一次拔出2放到最上面变成(2,3,1)，第二次拔出1放到最上面变成(1,2,3)。 给出初始顺序，帮助Alice计算最少移动次数。 输入 第一行包含一个整数N(N<=300000)。 接下来N行，每行一个整数，从上到下描述书柜中书的编号。 输出 输出一个整数表示最少移动次数。 样例输入 Copy 3 3 2 1 样例输出 Copy 2 提示 输入输出样例2： 输入：4 1 3 4 2 输出：2

Answer 1

请问，LZ有一些更复杂的测试数据吗？

以下是一个简短的代码，运行一下看看对不对。

var a:array[1..300000]of longint;
    s,n,i:longint;
begin
 readln(n); s:=n;
 for i:=1 to n do read(a[i]);
 for i:=n downto 1 do
  if a[i]=s then dec(s);
 writeln(s);
end.

追问

可不可以给点思路

追答

我无法证明以上算法的最优性。看着办吧：

把书本的排列看成一个队列，不过又有些特别：

    它只有一个入口（就是书堆的最上方），却有无穷多个出口（每本书都可以被抽出来），且一个元素一旦从某一出口中出来，就直接被塞入入口（放到书堆最上方）：

      上述队列中，已经随机插入了1~11的11个元素，现在，我们要通过规则将队列内的元素变为1→11的有序排列。

分析：

1. 最大的数是11，因此，“11”这个元素一定要移到最右边，即，“11”右边的所有数（这个例子中，是“1”）都要移出来，从左边插入队列（先不考虑顺序）；
   

2. 之后，比11小1的数是10，而10一定要排在11的左边，因此10到11之间的所有元素（此处是7、6），也要移出来，从左边插入队列（也先不考虑顺序）；

3. 继续分析“9”；

4. 当分析“8”时，发现“8”不在当前序列中“9”的左边，于是我们知道了：第一步就是“让8从队列中来，再从左边插入队列”；

5. “7”也是如此；

6. ……

7. 因此，我们总结出一个很可能是最快的排列方法：

   8出列；7出列；6出列；5出列……1出列。（注意：出列后，就会直接从左边插入）

        一共8步。

       尽管第一步“8出列又从左边插入”后，8和9之间还隔了5和2，但是后两个元素都会在之后的步骤中出列，因此8、9之间终究会没有障碍。