问题描述
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
分析 & 代码
思路：可以先计算最大的点与最小的点之间的区间距离，然后将所有的点之间的区间长度从大到小依次删除，知道划分为m段，也就是一开始得到的是一条线段（覆盖所有的区间），然后减去一段最大的区间距离，这时候原来的那条线短就变成了两段….以此类推直到成为m段。
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define inf 0x3f3f3f3f
int n,m;
int sav[205]; //保存点
int minu[205]; //保存区间长度
int maxx;
int minn;
bool cmp(int a, int b){
return a>b;
}
int main(){
int len;
while(cin>>n>>m){
maxx = -inf;
minn = inf;
for(int i=0; i<n; i++){
cin>>sav[i];
if(sav[i]>maxx)
maxx = sav[i];
if(sav[i]<minn)
minn = sav[i]; //先找到最大点 与最小点
}
len = maxx + 1 -minn; //注意因为是区间 所以不是直接相减 还要多减1
sort(sav, sav+n); //对点进行排序
for(int i=1; i<n; i++){
minu[i-1] = sav[i]-1-sav[i-1]; //计算区间
}
sort(minu, minu+n-1, cmp);
int i =0;
while(m!=1){ //直到一条线段（长度为len）划为m条线段
len -= minu[i++];
m--;
}
cout<<len<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116781.html
