a856:
分配曲奇1～
Content
這題和 分配曲奇2 的唯一差別在於士兵們的站法。這裏他們直線排開。
這一天，紅藍軍團的 n 個士兵排成了一列，由左至右按 1, 2, ..., n 編號。為了犒賞他們，長官決定給每人分派剛好一個曲奇。我們知道，只有部分士兵負責到飯堂取曲奇分配給眾人，而且每位士兵拿的曲奇數目可能不同。唯一可以確定的是他們共帶回 n 個曲奇。回到隊伍後，他們便用一個特殊的方法分發曲奇：每次，士兵可以把手上的一個曲奇傳給他身邊 (左邊或右邊) 的某人。由於大家都很餓，士兵們希望知道傳遞次數和的最小值。
準確地說，在眾人回到隊伍後，我們剛好有 n 個曲奇，其中第 i 個在隊列第 pi 號士兵手上。每次操作相當於令剛好一位士兵把手上的一塊曲奇傳給相鄰的人。請求出使每人都得一塊曲奇的最小操作次數。
Input
第一行有一正整數 T (1 <= T <= 50)，表示接下來有 T 組獨立的測資。（需要應答 T 次）
每個測資中共兩行。第一行給定一個整數 n (士兵和曲奇的數目)；第二行則給 n 個整數（以空格隔開），依次表示每個 pi，
1 <= n <= 105, 1 <= pi <= n。
Output
共輸出 T 行，分別為 T 個測資的答案。對第 i 個測資輸出傳遞次數之和的最小值。
Sample Input
#1
2 4 1 2 1 3 4 3 2 2 3
Sample Output
#1
3 2
Sample Input
#2
4 5 1 2 3 4 5 5 4 3 1 4 1 6 3 6 2 1 6 1 3 3 3 3
Sample Output
#2
0 2 4 3
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1K
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <1M
不公開 測資點#4 (20%): 1.0s , <50M
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1K
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <1M
不公開 測資點#4 (20%): 1.0s , <50M
Hint ：
在範例輸入#1中，對第一個測資我們可以把第一個曲奇向右傳遞三次，或者可以把第二、三、四個曲奇各向右傳遞一次；第二個測資中，可把第三個曲奇向左傳一次和把第四個曲奇向右傳一次。
在範例輸入#2中，對第二個測資可把第一個和第五個曲奇各向右傳一次；第三個測資中士兵們可以將第四個曲奇向右傳遞三次，再把第二個曲奇向左移一次。
其餘測資情況類似。注意某些測資中達到最小步數的方法不唯一。
出處:
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
| 1721 | a856 | 34 | 2024-11-28 12:47 |