遇到一个求差值总和问题，求解答。
在一个课堂上，有n个学生(1<=n<=3e5)，每个学生都有他们自己的学分ai(1<=ai<=1e9,ai<=ai-1)，现在老师想将他们分为 m个小组 (1<=m<=n)，为了方便交流，所有的小组都是由相邻的学生组成 (abc 相邻 , 不存在 ac 一个小组 b 在另一个小组的情况 )，现在老师想让每个小组的学分差值尽量小 ( 最大值减去最小值 )，请你帮助老师来分一下组，输出最后的每个小组的最小的差值的总和。 第一行和第二行输入两个数n、m表示有n个学生要分成m个小组，再输入n个数，表示每个学生的学分。 输出一个数字，表示最后分出的 m 个小组的最小的差值的总和。
写回答
-
因为题目中说了 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个最大的就好了。 输入：5 3 [1,3,5,7,9] 输出：4
2021-12-23 18:31:09赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
