一个空间建多个网站,深圳 教育集团网站建设,开发板有哪些,网站建设否定关键词区间覆盖问题 Time Limit: 1000MS Memory Limit: 65536KBSubmit Statistic DiscussProblem Description 用i来表示x坐标轴上坐标为[i-1#xff0c;i]的长度为1的区间#xff0c;并给出n#xff08;1≤n≤200#xff09;个不同的整数#xff0c;表示n个这样的区间。 现在要… 区间覆盖问题 Time Limit: 1000MS Memory Limit: 65536KBSubmit Statistic DiscussProblem Description 用i来表示x坐标轴上坐标为[i-1i]的长度为1的区间并给出n1≤n≤200个不同的整数表示n个这样的区间。 现在要求画m条线段覆盖住所有的区间 条件是每条线段可以任意长但是要求所画线段的长度之和最小 并且线段的数目不超过m(1≤m≤50。 Input
输入包括多组数据每组数据的第一行表示点n和所需线段数m后面的n行表示点的坐标Output
输出每组输出占一行表示线段的长度。Example Input 5 3
1 3 8 5 11 Example Output 7 #include stdio.hvoid sort(int value[],int n)
{int i,j,temp;for(i 0;i n-1;i)for(j 0;j n-1-i;j)if(value[j] value[j1]){temp value[j];value[j] value[j1];value[j1] temp;}
}int main()
{int num,amount;while(scanf(%d %d,num,amount) ! EOF){int i,sum 0;int position[1000],distance[1000];for(i 0;i num;i)scanf(%d,position[i]);if(amount num){printf(%d\n,num);}else{sort(position,num);for(i 0;i num;i)distance[i] position[i] - position[i1] -1; //求区间的间隔sort(distance,num);sum position[0] - position[num-1] 1; //求线段总长度i 1;while(i amount) //控制线段段数{sum sum - distance[i-1] ;i;}printf(%d\n,sum);}}return 0;
}
