记录编号	212814	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]跳石头	最终得分	100
用户昵称	ミント	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2015-12-08 15:30:04	内存使用	2.22 MiB

#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

ifstream fin("2015stone.in");
ofstream fout("2015stone.out");

const int maxn = 500000 + 2 + 200;
int stone[maxn];
int l, n, m;

int main()
{
	memset(stone, 0, sizeof(stone));
	
	fin>>l>>n>>m;
	
	for(int i=1;i<=n;i++)
		fin>>stone[i];
	
	stone[0] = 0;
	stone[n+1] = l;
	n += 2;
	
	sort(stone, stone+n, less<int>());
	
	int left = 0;
	int right = l + 1;
	
	while(right>left+1)
	{
		bool flag = true;
		
		int mid = (left+right)/2;
		
		int pos = 0;
		for(int i=1;i<n-m;i++)
		{
			int now = pos + 1;
			
			while(now<n&&stone[now]-stone[pos]<mid)
				now++;
			
			if(now==n)
			{
				flag = false;
				break;
			}
			
			pos = now;
		}
		
		if(flag)
			left = mid;
		else
			right = mid;
	}
	
	fout<<left<<endl;
	
	
	fin.close();
	fout.close();
	
	return 0;
}