区间覆盖问题

区间覆盖问题

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

用i来表示x坐标轴上坐标为[i-1，i]的长度为1的区间，并给出n（1≤M≤200）个不同的整数，表示n个这样的区间。 现在要求画m条线段覆盖住所有的区间， 条件是：每条线段可以任意长，但是要求所画线段的长度之和最小， 并且线段的数目不超过N(1≤N≤50）。

输入

输入包括多组数据，每组数据的第一行表示点n，和所需线段数m，后面的n行表示点的坐标

输出

输出每组输出占一行表示线段的长度。

示例输入

5 3 1 3 5 8 11

示例输出

7

/思路：只要将最长长度求出来，然后求出每两个区间距离， //最后用sum减去m-1个最大的两个区间的距离。

#include <cstdio> #include <string> #include <queue> #include <cmath> #include <stack> #include <vector> #include <algorithm> #include <map> using namespace std; #define INF 0x3f3f3f3f #define CLR(a,b) memset(a,b,sizeof(a)) #define PI acos(-1.0) #define LL long long int main(void){ freopen("题.txt", "r", stdin); int n, m; int arr[201], mid[200]; int i, j; int sum; while(scanf("%d%d", &n, &m) != EOF){ j = 0; sum = 0; for(i = 0; i < n; i++){ scanf("%d", &arr[i]); } sort(arr, arr + n); for(i = 1; i < n; i++){ mid[j++] = arr[i] - arr[i-1]-1; } sort(mid, mid + j); sum = arr[n-1]; for(i = j-1; i > j - m; i--){ sum -= mid[i]; } printf("%d\n", sum); } return 0; }