打敗了蘿莉後,那個長髮的女學生瞬間清醒了……原來她是個有強大法力的女學生叫作楓音,她也是在不知不覺中被控制了,因為她魔法很
強,所以敵人讓她在屋頂上監視著全校,同時還派了那蘿莉來控制她。
不過現在蘿莉被打敗了,還在喘息著,楓音也解除控制了!!!
於是妁艷和楓音決定要再進攻,一口氣把那蘿莉收服。因為那蘿莉不是學校的學生,是真的敵人,所以說不定能得到跟多消息!!!
楓音可以使出強大的魔法陣來攻擊敵人,不過這魔法陣很特別,它是一個由許多凹洞圍成的圓圈,而凹洞上面還要放魔法石,最後才能攻
擊。
每一個凹洞跟左右兩個洞都會有距離。也就是說,放了一些魔法石後,一個魔法石跟隔壁兩個魔法石也會有一些距離(可能會經過沒有魔法
石的凹洞,不過凹洞可以不算在距離內)。
而現在楓音要準備念咒語,所以給了妁艷一些魔法石,要妁艷把魔法石擺到一些洞上面,不過為了讓魔法更集中,希望能讓法石的”消失
度”越小越好。”消失度”要怎麼算呢?對於一個法石,把”它和左邊法石的距離”及”它和右邊法石的距離”加起來就是了。
希望在所有法石中,消失度最大的那個值能最小,法力會最好。
現在告訴你所有凹洞之間的距離,和法石的數量,請你讓最大消失度的值最小,並輸出那最大的消失度。
還有第一個洞跟第二個洞一定要擺魔法石!
含多筆測資!
每一筆的第一行有兩個數字N ,M (4≤N,M≤30000)
N代表凹洞的數量(包括一定要擺的洞)
M代表魔法石的數量(包括一定要擺的魔法石)
再來一行會有N個數字(1≤數字≤30000)
第i個數字代表第i個洞跟第i+1個洞之間的距離,第N個數字則代表第N個洞跟第1個洞之間的距離
每一筆測資皆要輸出一行
請讓最大的"消失度"最小
並輸出此"消失度"
2024/03/14 Update by FHVirus: 題目中沒有說明,不過「和左/右邊法石的距離」意思其實是「和左/右邊有放法石的洞的距離」,也可以理解成「一個洞只能放一個法石」。
原TIOJ1759 / problem setter: lnsuyn
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 20 |
2 | 1 | 20 |
3 | 2 | 20 |
4 | 3 | 20 |
5 | 4 | 20 |