| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10922 | Insertion Sort |
|
| 12224 | Doubly Linked List |
|
Description
實作插入排序法讓一個序列的數字遞增，並輸出數字總共交換了幾次。
比如說一個序列1 3 7 9 2，前四個數字都已經排好了，這時候第五個數字2進來，他必須跟9,7,3交換使得序列變成1 2 3 7 9。這個數字2的交換次數就是3次。
Input
輸入第一行為一個數字T，代表測試資料的筆數。接下來有T筆測資，每筆測資第一行為一個正整數N，表示這筆測資有N個數字。每筆測資的第二行會有N個數字，每個數字間以空格隔開。
數字範圍：
0 < N <= 100
0 <= 序列內的數字 <= 1000000
Output
輸出一行數字，將每筆測資的答案加總後輸出。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Maintain a doubly linked list, which supports the following operations:
(1) IH i : Insert a new integer i to the head of the list.
(2) IT i : Insert a new integer i to the tail of the list.
(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.
(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.
(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.
To improve the performance, it is suggested that three pointers be maintained in case4: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.
Input
There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains OP operations, and it is terminated by end-of-file (EOF). You may assume that i is a nonnegative integer not greater then 100000. The list is initially empty.
For case1 and case2, 1<=OP<=1000
For case3, 1<=OP<=10000, For each S operation, O(n) is also accepted.
For case4 and case5, 1<=OP<=500000, each operation should be done in O(1).
Output
For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
For RH and RT operation: if the list is empty, print a blank line.