哈尔滨模板网站建设,微信小程序怎么申请注册,wordpress4.6免费主题,营销网站制作皆选ls15227负责问题描述 小蓝是一个热爱收集玩具的小伙子#xff0c;他拥有 n 个不同的玩具。
这天#xff0c;他把 n 个玩具按照高度顺序从矮到高摆放在了窗台上#xff0c;然后#xff0c;他希望将这些玩具分成 k 个段#xff0c;使得所有分段的极差之和尽可能小。
具体来说…问题描述 小蓝是一个热爱收集玩具的小伙子他拥有 n 个不同的玩具。
这天他把 n 个玩具按照高度顺序从矮到高摆放在了窗台上然后他希望将这些玩具分成 k 个段使得所有分段的极差之和尽可能小。
具体来说你需要将一个长度为 n 的序列分为 k 段我们定义 Gi 为第 i 个分段的极差你要最小化 。
你能帮助小蓝找到最小值是多少吗
极差是指每个分段中最高和最矮玩具高度之差例如有一段为 {3,6,10,12}那么极差为 12−39。
分段即每一段在原始序列中是一段连续区间例如将 {1,2,3,4,5} 分为两段 {1,2,3}∣{4,5} 是合法的但是 {1,2,4}∣{3,5} 不是合法的。
输入格式 第一行输入两个整数 n,k代表玩具数量和需要分段的数量。
第二行输入 n 个整数 {h1,h2,...,hn}代表每个玩具的高度。
输出格式
输出一个整数表示最小的极差和。 样例输入 5 2
2 5 7 10 13样例输出 8 说明
存在多种分段方式其结果都是最小值
{2}∣{5,7,10,13}极差和为 088。{2,5,7}∣{10,13}极差和为 538。{2,5,7,10}∣{13}极差和为 808。
评测数据范围
1≤k≤n≤10^5。
1≤h1≤h2≤h3≤...≤hn≤10^9。 import java.util.*;public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int nscan.nextInt();int kscan.nextInt();int sum0;int a[]new int[n];int b[]new int[n-1];for(int i0;in;i){a[i]scan.nextInt();}for(int i0;in-1;i){b[i]a[i1]-a[i];}Arrays.sort(b);for(int i0;in-k;i){sumb[i];}System.out.println(sum);}
}
