区间覆盖问题-贪心

题目：

i表示x坐标轴上坐标为（i-1,i），长度为1的区间，给出n个这样的区间，要求画出m条线段覆盖住所有的区间，每条线段可以任意长，要求所有的线段长度和最小

第一行输入n和m，其中1<=n<=200，1<=m<=50

第二行输入n个坐标

思路：

我先用一条线段从起点拉到终点，将所有的区间都覆盖到，题目要求可以用m段并且和要最小，那我就将这一条线段从中间剪成m段，即剪m-1次

如果要想达到和最小的目的，那我每次剪开的地方一定要是最长的，我可以将所有空白的区间按长度递减排序，取前m-1个剪掉即可。

上代码：

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 #define MAX 205
 5 using namespace std;
 6 //此结构体用来记录空白段
 7 struct Node {
 8     int b;//起始坐标
 9     int e;//结束坐标
10     int len;//空白段长度
11     bool operator<(const Node &s)const {
12         return len > s.len;//长度按递减排序
13     }
14 };
15 Node node[MAX];
16 int k = 0;
17 int main() {
18     int n;
19     int m;
20     int a[MAX];
21     cin >> n >> m;
22     vector<int> v;
23     for (int i = 0; i < n; i++) {
24         cin >> a[i];
25         v.push_back(a[i]);
26     }
27     sort(v.begin(), v.end());
28     vector<int>::iterator it;
29     for (it = v.begin(); it != v.end()-1; it++) {
30         node[k].b = (*it);
31         node[k].e = *(it + 1)-1;
32         node[k].len = node[k].e - node[k].b;
33         k++;
34     }
35     int sum = 0;
36     sum = node[k - 1].e + 1 - node[0].b + 1;
37     sort(node, node + k);
38     for (int i = 0; i < k; i++) {
39         cout << node[i].b<<" "<<node[i].e<<" "<<node[i].len<<endl;
40     }
41     for (int i = 0; i < m - 1; i++) {
42         sum -= node[i].len;
43     }
44     cout << sum;
45 
46     return 0;
47 }