HDU Reorder the Books

Reorder the Books

By davidlee1999WTK

把這題的模型簡化一下，有一個1\rightarrow n1→n的排列形成的數列，我們要用最少的操作次數把這個數列排序，每次操作都是把一個數放到整個數列的最前面。 首先我們可以注意到每個數最多隻會被操作一次。因為假如有一個數被往前拿了兩次，顯然第一次的操作是沒有意義的。 然後能發現一定先操作大的數，再操作小的數。因為假如先把小的數放前面去了，再把大的數放前面去，小的數就又在大的數後面了，小的數必定還得再操作一次，然而操作兩次是不劃算的。

到這裡，對于19的資料範圍，我們有一個很暴力的做法，2^n2​n​​枚舉要操作哪些數，這些操作按數的大小從大往小的順序，模拟一下，然後檢查一下最後的序列是否有序，複雜度O(n*2^n)O(n∗2​n​​)。

我們很快又能發現，假如操作了大小等于kk的數，那麼所有小于kk的數也都得操作了。是以我們不用2^n枚舉，直接mm從11開始從小到大枚舉，表示要操作前mm小的數，然後模拟，驗證，這樣複雜度為O(n^2)O(n​2​​)。

不過其實mm也是不用枚舉的。 首先可以發現最大的數nn是不用操作的（其他數操作好了，數"nn"自然就在最後面了）。 于是我們先找到最大的數"nn"的位置，從這個位置往前找，直到找到(n-1)(n−1)。假如找到頭也沒找到(n-1)(n−1)，那麼數"(n-1)(n−1)"需要操作，而一旦操作了(n-1)(n−1)，根據前面結論，總共就需要(n-1)(n−1)次操作了;假如找到了(n-1)，那麼數"(n-1)(n−1)"也不需要操作（和數"nn"不需要操作一個道理）。 同理，我們接着從(n-1)(n−1)的位置往前找(n-2)(n−2),再從(n-2)(n−2)的位置往前找(n-3)(n−3)...假如數kk找不到了，那麼就至少需要kk次操作。這種做法的複雜度是O(n)O(n)的

:這題寫到代碼不過沒時間了，現在反思一下，什麼導緻無端的時間開銷？作為一個菜鳥的确靠着碰運氣的思考方式，沒有深入研究題目的本質。

剛開始覺得是逆序數，後來找到N^2的方法，于是下手寫，寫得模拟，但是無奈寫得太挫，改來改去，最後等50分猛然發現O（N）的規律。思維深度不夠，還缺乏鍛煉。。。。。