http://codeforces.com/problemset/problem/1110/B

 

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

方法：想象先用最长的m长度补好1~m位置，然后将最大的k-1个非缺口段挖去，就是答案。

一开始想二分：一次最长使用长度为x的用来补的长条，反例：k=3，  1 2 3 4 6 8  应该补1234一块，6一块，8一块。

#include<bits/stdc++.h>
using namespace std;

int n,m,k,a[100000+1000],d[100000+1000],ans;

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)d[i]=a[i+1]-a[i];
	ans=a[n]-a[1]+1;
	sort(d+1,d+1+n);
	for(int i=n;i>n-k+1;i--)ans-=d[i]-1;
	cout<<ans<<endl;
	return 0;
}