回分類題庫
g059: A.草地上的松鼠
關鍵字: NPSC 2009 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 200 Times / 174 Users | Submit : 609 Times / 195 Users | Accepted rate : 89%
題目加入時間 : 2011-12-26 15:09

Content: 简体中文

前一陣子松鼠王爬到樹林中最高的地方,他發現遠處有一片優美舒適的草地,於是他帶著整群松鼠去那邊玩耍。

玩了幾天,大家都累了,現在松鼠王想要帶著整群松鼠回到他們原本住的樹林。為了避免有些松鼠太貪玩而落單,松鼠王決定叫大家先整隊排成一列,確定全部到齊以後再一起出發。

現在大家已經集合並且排好隊了,正要出發的時候卻發現有一隻小松鼠不見蹤影。在這焦急的當下,松鼠王眼尖地發現這隻小松鼠還在草叢裡舒服地睡覺。為了維持松鼠王國的紀律,松鼠王必須把它叫醒。不過為了維持親民的形象,松鼠王不能生氣。

在把這隻小松鼠叫醒以後,松鼠王要讓他排到隊伍的某個地方。他不能排在隊伍的最前面,因為需要專業的嚮導帶領大家回去。他也不能排在最後面,以免因為打瞌睡而倒在半路上。由於其他松鼠已經排好隊,要在他們之中挪出一些空間給這隻小松鼠也有點困難。

聰明的松鼠王想到了一個好辦法:在所有相鄰的松鼠中找出距離最遠的兩個,然後就讓這隻小松鼠排在他們中間。這裡距離的定義是兩隻松鼠所在位置的差的絕對值。

由於松鼠的數量有點多,隊伍也很長,松鼠王需要你的幫忙才能很快地知道這隻小松鼠應該排在哪裡。

Input:

第一行有一個整數T,代表接下來有幾組測試資料。
每一筆測試資料有兩行,第一行有一個數字N,代表隊伍上排了幾隻松鼠。
第二行有N 個整數,x1, x2,…, xn,分別代表這N 隻松鼠的位置。
數字越小的表示在隊伍的越前面。
(2 <= N <= 10000,0 <= x1 < x2 < … < xn <= 200000000)

Output:

對每筆測試資料請輸出一個整數k,代表這隻小松鼠應該被排在第 k 隻松鼠和第k + 1隻松鼠中間。若有距離相同的情形,請讓這隻小松鼠排在越前面越好。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
1
5
1 3 6 8 9

Sample Output :

2

Hint :

Author :

NPSC 2009 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum