首页 > 试题广场 >

施魔法

[编程题]施魔法

热度指数：18 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛可乐有 n 个元素( 编号 1..n )，第 i 个元素的能量值为 $a_i$ 。
牛可乐可以选择至少 k 个元素来施放一次魔法，魔法消耗的魔力是这些元素能量值的极差。形式化地，若所用元素编号集合为 S，则消耗的魔力为 $\max_{i\in S}\{a_i\}-\min_{i\in S}\{a_i\}$ 。

牛可乐要求每个元素必须被使用恰好一次。
牛可乐想知道他最少需要多少魔力才能用完所有元素，请你告诉他。

输入描述:

第一行两个正整数  。

第二行 n 个整数 。

保证 ，。

输出描述:

输出一行，一个整数表示答案。

示例1

输入

4 2
8 7 114514 114513

输出

说明

使用第 1、2 个元素施放一次魔法，消耗魔力为 8-7=1；第 3、4 个元素施放一次魔法，消耗魔力为 114514-114513=1；两个魔法一共消耗 2 点魔力。

算法知识视频讲解

--嘤色暴撃--

发表于 2020-02-06 21:27:49

dp 第一眼看到这道题还以为是标准的划分dp，弄了好久时间复杂度还是超现在总算懂了，这题是的dp首先我们需要排序，把这些元素从小到大排好，这样确保可以直接划分(自己想一下)，并且这一段的最大值是这一段的尾，最小值是这一段的头，相当于连区间最大值最小值的线段树都不用打了用表示前个元素以为尾划分段后的最展开全文

QQQQwQQQQ

发表于 2020-02-07 18:16:50

施魔法https://ac.nowcoder.com/acm/contest/3003/H 先从小到大排序，极差转换为--连续一段数尾部和开头的差值DP[i]就是前i个元素以i为尾划分段的最小值i可以是作为前一段的新尾，DP[i]=DP[i-1]-A[i-1]+A[i]也可是新开一段k，作为段尾展开全文