区间覆盖问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 用i来表示x坐标轴上坐标为[i-1，i]的长度为1的区间，并给出n（1≤n≤200）个不同的整数，表示n个这样的区间。 现在要求画m条线段覆盖住所有的区间， 条件是：每条线段可以任意长，但是要求所画线段的长度之和最小， 并且线段的数目不超过m(1≤m≤50）。
Input 输入包括多组数据，每组数据的第一行表示区间个数n和所需线段数m，第二行表示n个点的坐标。 Output 每组输出占一行，输出m条线段的最小长度和。 Sample Input 5 3 1 3 8 5 11 Sample Output 7 Hint 注意：题目数据已于2018.4.16更新 Source
import java.util.*; class myclass { int arr[]; int n; int b[]; int m; myclass(int a[], int n, int m) { this.arr = a; this.n = n; b = new int[205]; this.m = m; } void sort(int a[], int n) { int i, j; int t; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { t = a[j + 1]; a[j + 1] = a[j]; a[j] = t; } } } } void main() { int s, e; sort(this.arr, this.n); s = arr[0]; e = arr[this.n - 1]; for (int i = 0; i < this.n - 1; i++) { b[i] = arr[i + 1] - arr[i] - 1; // System.out.println(b[i]); } sort(b, n - 1); int i; i = n - 2; int l = arr[n - 1] - arr[0] + 1; m--; while (m > 0) { l -= b[i--]; m--; } System.out.println(l); } } class Main { public static void main(String[] args) { Scanner ss = new Scanner(System.in); int n, m; final int mm = 205; while (ss.hasNextInt()) { n = ss.nextInt(); m = ss.nextInt(); int i, j; int s, e; int a[] = new int[mm]; int b[] = new int[mm]; for (i = 0; i < n; i++) a[i] = ss.nextInt(); if (m == n) { System.out.println(m); } else { myclass per = new myclass(a, n, m); per.main(); } } ss.close(); } }