k601. 分配曲奇1
Tags :
Accepted rate : 11人/12人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-05-24 19:32

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
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :

在範例輸入中,對第一個測資我們可以把第一個曲奇向右傳遞三次,或者可以把第二、三、四個曲奇各向右傳遞一次;第二個測資中,可把第三個曲奇向左傳一次和把第四個曲奇向右傳一次。

Tags:
出處:
[管理者: 1450840-0@g. ... (肥余好朋友) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」