CCF-CSP 最大波動與中間數
摘要：
CCF-CSP 201609-1 最大波動 與 201612-1 中間數 題解
201609-1 最大波動
問題描述
試題編號：201609-1
試題名稱：最大波動
時間限制：1.0s
記憶體限制：256.0MB
問題描述
小明正在利用股票的波動程度來研究股票。小...
201609-1 最大波動
問題描述
試題編號：201609-1 試題名稱：最大波動 時間限制：1.0s 記憶體限制：256.0MB 問題描述 小明正在利用股票的波動程度來研究股票。小明拿到了一隻股票每天收盤時的價格，他想知道，這隻股票連續幾天的最大波動值是多少，即在這幾天中某天收盤價格與前一天收盤價格之差的絕對值最大是多少。 輸入格式 輸入的第一行包含了一個整數n，表示小明拿到的收盤價格的連續天數。 第二行包含n個正整數，依次表示每天的收盤價格。 輸出格式 輸出一個整數，表示這隻股票這n天中的最大波動值。 樣例輸入 6 2 5 5 7 3 5 樣例輸出 4 樣例說明 第四天和第五天之間的波動最大，波動值為|3-7|=4。 評測用例規模與約定 對於所有評測用例，2 ≤ n ≤ 1000。股票每一天的價格為1到10000之間的整數。
題解
這個題目也很簡單，只要遍歷輸入的價格列表，得到元素與下一個元素差值的絕對值，不斷地比較絕對值，得到最大的差值，即為最大的波動值。
n = int(input())# 獲取天數 lst = list(map(int, input().split()))# 獲取價格列表 res = 0 for i in range(n - 1):# 遍歷價格列表 tmp = abs(lst[i] - lst[i + 1])# 取差值 if tmp > res:# 比較大小 res = tmp# 較大的差值 print(res)# 輸出最大差值
201612-1 中間數
問題描述
試題編號：201612-1 試題名稱：中間數 時間限制：1.0s 記憶體限制：256.0MB 問題描述 在一個整數序列a1, a2, …, an中，如果存在某個數，大於它的整數數量等於小於它的整數數量，則稱其為中間數。在一個序列中，可能存在多個下標不相同的中間數，這些中間數的值是相同的。 給定一個整數序列，請找出這個整數序列的中間數的值。 輸入格式 輸入的第一行包含了一個整數n，表示整數序列中數的個數。 第二行包含n個正整數，依次表示a1, a2, …, an。 輸出格式 如果約定序列的中間數存在，則輸出中間數的值，否則輸出-1表示不存在中間數。 樣例輸入 6 2 6 5 6 3 5 樣例輸出 5 樣例說明 比5小的數有2個，比5大的數也有2個。 樣例輸入 4 3 4 6 7 樣例輸出 -1 樣例說明 在序列中的4個數都不滿足中間數的定義。 樣例輸入 5 3 4 6 6 7 樣例輸出 -1 樣例說明 在序列中的5個數都不滿足中間數的定義。 評測用例規模與約定 對於所有評測用例，1 ≤ n ≤ 1000，1 ≤ ai ≤ 1000。
題解1
最簡單的辦法就是統計每個元素的以下資訊：（1 大於該元素的元素個數（記作 gt ），（2 小於該元素的個數(記作 lt )，如果 gt 等於 lt 且不等於 0，則認為已經找到中間數，設定標誌位為1，輸出中間數，並且結束遍歷。如果遍歷完所有的元素，標誌位還沒有被置為 1，即沒有找到中間數，則輸出 -1 。
n = int(input())# 獲取整數個數
L = list(map(int, input().split()))# 獲取整數序列
gt = 0
lt = 0
flag = 0# 標誌是否找到中間數
for i in range(n):
for j in range(n):
if L[i] < L[j]:# 統計大於該元素的元素個數
gt += 1
if L[i] > L[j]:# 統計小於該元素的元素個數
lt += 1
if gt == lt and gt != 0:# 大於的個數和小於的個數相等，且不為0
print(L[i])# 輸出中間數
flag = 1# 標誌已經找到
break# 結束迴圈
gt = 0# 重置
lt = 0
if flag == 0:# 沒有找到中間數
print('-1')
題解2
另一種辦法是，先對列表進行排序，然後找到排在中間的那個元素，即候選的中間數。然後，再遍歷列表將候選的中間元素與列表的每個元素進行比較並計數，判斷大於中間元素的個數是否等於小於它的個數，如果等於則該數就是中間數，輸出中間數，否則沒有中間數，輸出 -1 。
n = int(input())# 獲取整數個數 lst = list(map(int, input().split()))# 獲取整數序列 rst = lst.copy()# 複製列表，用於排序 rst.sort()# 排序，用於得到中間元素 lt = 0 gt = 0 for i in lst:# 這裡只需要一層迴圈 if rst[int(n / 2)] > i:# 統計小於中間元素的元素個數 lt += 1 elif rst[int(n / 2)] < i:# 統計大於中間元素的元素個數 gt += 1 if lt == gt: print(rst[int(n / 2)])# 輸出結果 else: print(-1)# 沒有找到中間數
知識點補充
copy() 函式
copy() 函式用於複製列表，它會返回複製後的新列表。
>>>lst = [1, 2, 3, 4] >>>lst.copy() [1, 2, 3, 4]
下面用一個例子來說明copy()
函式與切片、直接賦值的異同：
- copy ()函式
>>>lst = [1, 2, 3, 4] >>>rst = lst.copy() # 使用 copy() 函式複製 >>>rst [1, 2, 3, 4] >>>rst[1] = 5 >>>rst [1, 5, 3, 4] >>>lst# 修改複製後的列表，原列表值不變 [1, 2, 3, 4]
- 切片
>>>lst = [1, 2, 3, 4] >>>rst = lst[:] # 使用切片 >>>rst [1, 2, 3, 4] >>>rst[1] = 5 >>>rst [1, 5, 3, 4] >>>lst# 修改複製後的列表，原列表值不變 [1, 2, 3, 4]
- 直接賦值
>>>lst = [1, 2, 3, 4] >>>rst = lst # 直接賦值 >>>rst [1, 2, 3, 4] >>>rst[1] = 5 >>>rst [1, 5, 3, 4] >>>lst # 修改複製後的列表，原列表值也改變了 [1, 5, 3, 4]