赛后AC留念 - -
二分思路，当时写了一个贪心用堆维护，结果没考虑到两边距离一样的情况，只水了30分。
还有一年，明年继续努力吧
#include <iostream>
using namespace std;
long d[100001];
bool check(long dis,long n,long m)
{
long i,s,last;
last=0;
s=0;
for (i=1;i<=n;i++){
if (d[i]-last>=dis) last=d[i];
else s++;
}
if (s<=m) return true;
else return false;
}
main()
{
long l,m,n,i,L,R,MID;
ios::sync_with_stdio(false);
cin>>l>>n>>m;
for (i=1;i<=n;i++) cin>>d[i];
d[i]=l;
L=0; R=l;
while (R-L>1){
MID=(L+R)/2;
if (check(MID,n+1,m))L=MID;
else R=MID;
}
cout<<L<<endl;
}

二分很重要，二分很重要，二分很重要
另外边界处理不要写萎了

为什么我第一印象也是二分查找……最后又个小坑，就是末端点不能移走。如果最后一个应该到的节点到终点的距离小于预期值k就把最后一个节点（不是终点）删去，因为倒数第二个点到最后一个节点的距离一定会大于预期值k，所以要再删一个节点。

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<fstream>
using namespace std;

long n, l, m, minp, maxp, k,step,pay,d;
long a[1000006];

int main()
{
scanf("%ld%ld%ld", &l, &n, &m);
for (long i = 1; i <= n; i++)
scanf("%ld", &a[i]);
a[0] = 0;
maxp = l;
minp = 1;
while (minp < maxp)
{
k = (minp + maxp+1) / 2; //二分查找
step = 0;
pay = 0; //初始化

for (long i = 1; i <= n; i++)
{
if (a[i] - a[step]<k)
{
pay++;
if (pay > m)
break;
continue;
}
else
step = i;
}
if (((l - a[step] >= k) && pay <= m) || pay < m)
minp = k;
else maxp = k - 1;

}
printf("%ld", maxp);
system("pause");
return 0;
}

来自AU爷laekov的代码。。膜拜中Orzzzzzz

// Source code from laekov at noip 2015 day2
#define PRID "stone"
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 50003;

int n, m, l, a[maxn];

int checkStone(int lt) {
int s(0), po(0);
for (int i = 0; i < n; ++ i)
if (a[i] - po >= lt)
po = a[i];
else
++ s;
if (l - po < lt)
++ s;
return s;
}

int main() {
freopen(PRID ".in", "r", stdin);
freopen(PRID ".out", "w", stdout);
scanf("%d%d%d", &l, &n, &m);
for (int i = 0; i < n; ++ i)
scanf("%d", a + i);
int le(0), re(l);
while (le < re) {
int md((le + re + 1) >> 1);
if (checkStone(md) > m)
re = md - 1;
else
le = md;
}
printf("%d\n", le);
return 0;
}

二分查找
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
long long l,n,m;
long long d[50050];
long long merging(int ll,int rr)
{
if(ll>rr)
{
return 0;
}
long long mid=(ll+rr)/2;
int all=0;
int ans=0;
//memcpy(&s,&d,sizeof(d));
int last=0;
for(int i=1;i<=n;i++)
{
if(l-d[i]<mid)
{
all=all+(n-i+1);
break;
}
if(d[i]-last<mid)
{
all++;
}
else
{
last=d[i];
}
}
if(all>m)
{
if(ll==rr)
{
return 0;
}
ans=merging(ll,mid);
}
else if(all<=m)
{
if(ll==rr)
{
return mid;
}
else if(ll<rr)
{
ans=max(merging(mid+1,rr),mid);
}
}
return ans;
}
int main(){
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
scanf("%lld%lld%lld",&l,&n,&m);
//d=(long long )malloc(sizeof(long long)(n+3));
//s=(long long )malloc(sizeof(long long)(n+3));
// cout<<l<<n<<m;
for(int i=1;i<=n;i++)
{
scanf("%lld",&d[i]);
}
d[n+1]=l;
long long ans=merging(0,l);
cout<<ans;
return 0;
}

第4组wa求大神告知为什么
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int L, n, m;
int d[500001];
bool check(int x) {
int ans = 0, flag = 0;
for(int i = 0; i <= n; i++) {
flag = i;
for(int j = i + 1; j <= n; j++) {
if(d[j] - d[i] >= x) {
i = j - 1;
break;
}
if(j == n)
i = j;
if(d[j] - d[i] < x)
ans ++;
}
}
for(int i = flag; i <= n; i++)
if(L - d[i] < x)
ans ++;
else
break;
return ans <= m;
}
int main() {
cin >> L >> n >> m;
if(n == 0) {
cout << L << endl;
return 0;
}
int l, r;
l = r = L;
for(int i = 1; i <= n; i++) {
cin >> d[i];
l = min(d[i] - d[i - 1], l);
}
while(1 < r - l) {
int mid = (l + r) / 2;
if(check(mid) == 1)
l = mid;
else r = mid;
}
if(check(l) == 1)
cout << l << endl;
else
cout << r << endl;
//system("pause");
return 0;
}