e198: 課堂分組
Tags :
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-05-12 00:35

Content

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

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

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

Input

輸入首行有一個正整數$\color{black}{\space T(T\leq 20)\space}$,代表測資筆數。

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

次行有$\color{black}{\space N\space}$個正整數$\color{black}{\space p_1\sim p_N(1\leq p_i\leq 10^4)\space}$,代表編號$\color{black}{\space i\space}$的學生的實力值為$\color{black}{\space p_i\space}$。

Output

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

Sample Input
2
5 3 1
3 1 4 2 5
5 5 1
3 1 4 2 5
Sample Output
9
5
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (13%): 1.0s , <1K
不公開 測資點#1 (8%): 1.0s , <10M
不公開 測資點#2 (35%): 1.0s , <1M
不公開 測資點#3 (44%): 1.0s , <10M
Hint :

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

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

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

 

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

測資點$\color{black}{\space 0(13\%)\space}$:$\color{black}{\space N\leq 15\space}$。

測資點$\color{black}{\space 1(8\%)\space}$:$\color{black}{\space K=1,x=0\space}$。

測資點$\color{black}{\space 2(35\%)\space}$:$\color{black}{\space N\leq 2000\space}$。

測資點$\color{black}{\space 3(44\%)\space}$:無特別限制。

Tags:
出處:
板橋高中校友盃 [管理者:
baluteshih (波路特石)
]


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