筆試算法模拟題精解之“學習小組”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“131.學習小組”的解法探究。先來看一下題目内容：

題目詳情：

等級：中等

知識點：貪心

檢視題目：學習小組

在一個課堂上，有n個學生(1<=n<=3e5)，每個學生都有他們自己的學分ai(1<=ai<=1e9,ai<=ai-1)，現在老師想将他們分為m個小組(1<=m<=n)，為了友善交流，所有的小組都是由相鄰的學生組成(abc相鄰,不存在ac一個小組b在另一個小組的情況)，現在老師想讓每個小組的學分內插補點盡量小(最大值減去最小值)，請你幫助老師來分一下組，輸出最後的每個小組的最小的內插補點的總和。

第一行和第二行輸入兩個數n、m表示有n個學生要分成m個小組，再輸入n個數，表示每個學生的學分。

輸出一個數字，表示最後分出的m個小組的最小的內插補點的總和。

示例1

輸入：

5

3

[1,3,5,7,9]

輸出：

4

解題方法：

因為題目中說了ai是一個非遞減的數列，是以我們可以推導出一個式子。

比如我們要将一個數組分成3組，那麼可以假設為，[a1,ai],[ai+1,aj],[aj+1,an]這三組，然後我們所要求的值就是(ai - a1) + (aj - ai+1) + (an - aj+1) .

那麼就可以推導出an - a1 + aj - aj+1 - ai - ai+1，是以就是an - a1減去最大的m-1個相鄰的內插補點，那麼ai-ai+1這個顯然是差分的性質，是以我們對于原數列求一個差分數組出來，然後對差分數組進行排序，貪心的去減去前m-1個最大的就好了。

看完之後是不是有了答題思路了呢，快來練練手吧：

131.學習小組

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，定制衛衣、雙肩背包、機械鍵盤等多重好禮等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！