codeforces-1110B. Tape-题解

题目：

你有一根长棍，长为m。但是，有些部分已经损坏，需要修复。你有一个无限长的修复磁带。想从胶带上剪下一些，然后用它们盖住所有的碎片。您可以覆盖不间断段;也有可能一些胶带会重叠，这些零件的最小总长度是多少?

输入

第一行包含三个整数n，m，k——破碎的片段数量,棒的长度和部分可以使用的最大数量。

第二行包含n整数b1,b2,…,bn破碎段的位置。这些整数是按递增顺序给出的，即b1<b2<…<bn

输出

打印零件的最小总长度。

input：                                                                    

4 100 2                                                                          

20 30 75 80                                                                

output：                                                                     

17      

input：   

5 100 3      

1 2 4 60 87 

output：

6                                                                 

个示例中，可以使用一段长度11来覆盖破碎的段20和30，使用另一段长度6来覆盖75和80，总长度为17。

在第二个示例中，您可以使用一个长度为4的片段来覆盖断开的片段1、2和4，使用两个长度为1的片段来覆盖断开的片段60和87，共要6。

即：

一个长为m的木棍，有n个缺口，你最多可以用k个长条补缺口，问用来补缺口的长条最短是多少（ant）。

思路：

求出将相邻两个断点之间的距离，并进行排序，然后用数组a[i]来存，再计算从第一个断点到最后一个断点之间的距离（先用ant来存），最后用ant（从最长的片段开始）减去一定数量的片段。（数量的多少由k的值决定）

my code：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k,a[1000000],d[1000000],ant=0;
int main()
{
	cin>>n>>m>>k;
	for(int i=0;i<n;i++)//输入断点的位置，存入a[i] 
		cin>>a[i];
	for(int i=0;i<n;i++)
		d[i]=a[i+1]-a[i];//依次排列两断点之间的距离，存入d[i] 
	ant=a[n-1]-a[0]+1;//第一个断点与第二个断点之间的距离 
	sort(d,d+n);//将相邻断点间的距离大小排序（从小到大） 
	for(int i=n-1;i>n-k;i--)
		ant=ant-d[i]+1;
	cout<<ant<<endl;
	return 0;
}

​