e198. 課堂分組 - 高中生程式解題系統

內容

　　這天，特石想為他教導的 $N$ 個學生辦一場程式競賽，但不幸地是現在電腦教室正在進行校友盃(校友們都非常優秀，不方便打擾)，所以他們移駕到了另一間電腦分布很奇怪的電腦教室，這間教室所有電腦是連成一直線的，且不能移動位置；電腦們的編號為 $1 \sim N$ ，對於所有 $1 < i < N$ ，都滿足電腦 $i$ 的左邊是電腦 $i - 1$ 、右邊是電腦 $i + 1$ 。

　　學生們剛進教室就立刻全部坐定了位置，而且他們也不想再換位置，這時特石才發現，他忘記分組了，由於大家的實力不平均，盲目地亂分組只會導致隊伍不平衡，然而又不能讓不相鄰的學生同一組，這讓特石非常困擾。

　　已知坐在電腦 $i$ 的學生的實力值是 $p_{i}$ ，且特石訂定出了一組的誤差值計算方式，也就是該組所有學生的實力值總和與 $K$ 的絕對值再加上 $X$ ，你能夠告訴他，在最佳的分組方式下，每一組的誤差值總和最小可以是多少嗎？

輸入說明

輸入首行有一個正整數 $T (T \leq 20)$ ，代表測資筆數。

每筆測資首行有三個整數 $N, K, X (1 \leq N \leq 10^{5}, 1 \leq K \leq 10^{9}, 0 \leq X \leq 10^{9})$ ，意義如題目所述。

次行有 $N$ 個正整數 $p_{1} \sim p_{N} (1 \leq p_{i} \leq 10^{4})$ ，代表編號 $i$ 的學生的實力值為 $p_{i}$ 。

輸出說明

對於每筆測資，輸出在最佳的分組方式下，每一組的誤差值總和最小可以是多少。

範例輸入 #1

範例輸出 #1

9
5

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (13%): 1.0s , <1K
不公開測資點#1 (8%): 1.0s , <10M
不公開測資點#2 (35%): 1.0s , <1M
不公開測資點#3 (44%): 1.0s , <10M

提示：

　　第一筆範例測資中，分組方式如： ${1, 2}$ 、 ${3}$ 、 ${4, 5}$ ，總誤差值為 $(| 3 + 1 - 3 | + 1) + (| 4 - 3 | + 1) + (| 2 + 5 - 3 | + 1) = 9$ ，這同時也是誤差值總和最小的分組方式。

　　第二筆範例測資中，分組方式如： ${1, 2}$ 、 ${3, 4}$ 、 ${5}$ ，總誤差值為 $(| 3 + 1 - 5 | + 1) + (| 4 + 2 - 5 | + 1) + (| 5 - 5 | + 1) = 5$ ，這同時也是誤差值總和最小的分組方式。

　　請注意，同一組的人必定會是連續的一段區間。

　　本題共有四組測試題組，條件限制如下所示。每一組可對應到一或多筆測試資料。

測資點 $0 (13 %)$ ： $N \leq 15$ 。

測資點 $1 (8 %)$ ： $K = 1, x = 0$ 。

測資點 $2 (35 %)$ ： $N \leq 2000$ 。

測資點 $3 (44 %)$ ：無特別限制。

標籤:

出處:

板橋高中校友盃 [管理者： baluteshih (波路特石) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」