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;
}

​