过不了的人试试这组数据
30 5 3
2
7
17
27
29
答案是7
（这题真tm坑，用noip数据全过，用vijos数据就只有60分）

水题水题
NOIP2015Day2T1
这题一看就是二分答案：
1. 由于以最少的间距为自变量，需要拿掉的石头具有单调性，所以可以二分答案
2. 对于当前答案，我们可以贪心的来
3. 对于终点的特殊情况其实不特殊：如果终点要被拿掉，那么其实就是把终点前面那个拿掉
时间复杂度: O(n log L)
空间复杂度: O(n)

过路人，贴代码<1A><用时6分钟>

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=5e4+5,MaxL=1e9;
int n,m,L;
int dis[N];
int check(int d){
    int cnt=0,pos=0;
    for (int i=1;i<=n+1;i++)
        if (dis[i]-pos<d)
            cnt++;
        else
            pos=dis[i];
    return cnt;
}
int main(){
    scanf("%d%d%d",&L,&n,&m);
    for (int i=1;i<=n;scanf("%d",&dis[i]),i++);//专业压行 
    dis[n+1]=L;
    int ans=0,le=1,ri=MaxL,mid,need;
    while (le<=ri){
        mid=(le+ri)>>1;//等效于mid=(le+ri)/2
        need=check(mid);
        if (need<=m)
            le=mid+1,ans=mid;
        else
            ri=mid-1;
    }
    printf("%d",ans);
    return 0;
}

我发现凡是想不出来的题 就尝试二分答案
比如借教室，思想和这题惊人相似
思路：
二分最大的距离（答案）
看看符不符合要求
因为第一个石头不能动
所以如果第一个石头与第二个石头之间距离不符合要求
那么必须拿走第二个石头
以此类推 依次访问后面的石头
如果 某块石头与前一个石头的距离小了
我们有两个选择：拿走这个 或 拿走前一个
然而此时 拿走前一个可以增大当前这个不足的距离
但对前面的石头并无好处 因为前面的已经符合要求了
所以选择移动后一块石头 还可能对后面有好处
#include <cstdio>

int main(){
int lenth,n,m,p[50010];
scanf("%d%d%d",&lenth,&n,&m);
p[0]=0,p[n+1]=lenth;
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
int l=1,r=lenth,mid,last,move,ans;
while(l<=r){
mid=(l+r)/2;
last=0,move=0;
for(int i=1;i<=n;i++){
if(p[i]-p[last]<mid)
move++;
else
last=i;
}
if(p[n+1]-p[last]<mid)
move++;
if(move>m)
r=mid-1;
else{
ans=mid;
l=mid+1;
}

}
printf("%d",ans);
return 0;
}

var
a:array [0..100005] of longint;
v,n,p,i,l,r,m,u,s:longint;
begin
read(v,n,p);
for i:=1 to n do read(a[i]);
a[0]:=0; a[n+1]:=v; inc(n);
l:=1; r:=v;
while (l<r) do begin
m:=(l+r+1) div 2;
s:=a[0]; u:=0;
for i:=1 to n do
if (a[i]-s>=m) then s:=a[i] else inc(u);
if (u>p) then r:=m-1 else l:=m;
end;
write(l);
end.

简单二分

#include<iostream>
using namespace std;
int L,n,m;
int a[50002];

int p(int x)
{
    int p=0,q=0;
    for(int i=1;i<=n;i++)
    if(a[i]-p<x)    q++;
    else p=a[i];
    return q;
}

int main()
{
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    a[++n]=L;
    int l=0,r=L;
    int ans=-111;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int x=p(mid);
        if(x<=m)
        l=mid+1,ans=mid;
        else
        r=mid-1;
    }
    cout<<ans;
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

const int oo_min=0xc0c0c0c0,oo_max=0x3f3f3f3f;

namespace dts
{
    typedef long long ll;
    
    ll n,m,l;
    ll a[50000+1];
    
    ll check(ll v)
    {
        ll pos=a[0],ans=0;
        for (ll i=1;i<=n;i++)
            if (a[i]-pos<v)
                ans++;
            else
                pos=a[i];
        return ans;
    }
    
    ll work()
    {
        ll left,right;
        for (left=0,right=l;right-left>1;)
        {
            ll mid=(left+right)/2;
            if (check(mid)<=m)
                left=mid;
            else
                right=mid;
        }
        if (check(right)<=m)
            return right;
        else
            return left;
    }
    
    void main()
    {
        while (~scanf("%lld%lld%lld",&l,&n,&m))
        {
            a[0]=0;
            for (ll i=1;i<=n;i++)
                scanf("%lld",&a[i]);
            a[++n]=l;
            printf("%lld\n",work());
        }
    }
};

int main()
{
    dts::main();
}

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int a[50001],b[50001];
int k,n,m,x,l,r,mid,ans;
bool check(int mid)
{
    int s=0;
    int ss=0;
    for(int j=0;j<=n;j++)
    {
        ss+=b[j];
        if(ss<mid)
        {
            s++;
        }
        else
        {
            ss=0;
        }
    }
    if(s>m)
    {
        return false;
    }
    else
    {
        return true;
    }
}
int main()
{
    scanf("%d%d%d",&k,&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++)
    {
        b[i]=a[i+1]-a[i];
    }
    b[n]=k-a[n];
    l=0;
    r=1000000000;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)==true)
        {
            ans=mid;
            l=mid+1;
        }
        else
        {
            r=mid;
        }
    }
    printf("%d",ans);
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
//freopen("2015stone.in","r",stdin);
//freopen("2015stone.out","w",stdout);
int l,n,m;
int a[50002],cnt,x,y,mid,last,flag,ans;
scanf("%d%d%d",&l,&n,&m);
a[0]=0;
a[n+1]=l;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
x=0;
y=l;
while(x<=y){
flag=1;
cnt=0;
last=0;
mid=x+(y-x)/2;
for(int i=1;i<=n+1;i++){
if(a[i]-last<mid)
cnt++;
else
last=a[i];
if(cnt>m){
flag=0;
break;
}
}
if(flag){x=mid+1;ans=mid;}else y=mid-1;
}
printf("%d",ans);
}

#include<cstdio>
#define reg register
const int maxn=50001;
int len,m,n,mid;
int dis[maxn];
inline int check(int l,int r)
{
    mid=(l+r)>>1;
    reg int num=0,last=0;
    for(reg int i=1;i<=n+1;i++)
    {
        if(dis[i]-last<mid)
            num++;
        else
            last=dis[i];
    }
    if(num>m)
        return 0;
    else
        return 1;
}
int main()
{
    scanf("%d%d%d",&len,&n,&m);
    for(reg int i=1;i<=n;i++)
        scanf("%d",&dis[i]);
    dis[n+1]=len;
    int l=1,r=len,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(l,r))
        {
            ans=mid;
            l=mid+1; 
        }
        else
            r=mid-1;
    }
    return !printf("%d\n",ans);
}

#include<cstdio>
#define reg register
const int maxn=50001;
int len,m,n,mid;
int dis[maxn];
inline int check(int l,int r)
{
mid=(l+r)>>1;
reg int num=0,last=0;
for(reg int i=1;i<=n+1;i++)
{
if(dis[i]-last<mid)
num++;
else
last=dis[i];
}
if(num>m)
return 0;
else
return 1;
}
int main()
{
scanf("%d%d%d",&len,&n,&m);
for(reg int i=1;i<=n;i++)
scanf("%d",&dis[i]);
dis[n+1]=len;
int l=1,r=len,ans;
while(l<=r)
{
mid=(l+r)>>1;
if(check(l,r))
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
return !printf("%d\n",ans);
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 50005;

int d[M], len, n, m;

bool check(int x){
int past = 0, tot = 0;
for(int i = 1; i <= n + 1; i++)
if(d[i] - past < x)
tot++;
else
past = d[i];
return tot <= m;
}

int main()
{
scanf("%d%d%d", &len, &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &d[i]);
d[n+1] = len;
int l = 1, r = len, ans;
while(l <= r){
int mid = l + r >> 1;
if(check(mid))
ans = mid, l = mid + 1;
else
r = mid - 1;
}
printf("%d", ans);
return 0;
}

二分法
const maxn=50009;
var a:array[0..maxn]of longint;
i,l,n,m,left,right,mid:longint;
function tri(mid:longint):boolean;
var count,pre,next:longint;
f:array[0..maxn]of boolean;
begin
tri:=false;
fillchar(f,sizeof(f),true);
i:=0;next:=1;count:=0;
while next<=n do
begin
while (a[next]-a[i]<mid)and(next<=n) do
begin
f[next]:=false;
inc(next);
inc(count);
end;
i:=next;next:=i+1;
end;
i:=n;
while not f[i] do
dec(i);
if a[n+1]-a[i]<mid then inc(count);
if count<=m then tri:=true;
end;
begin
assign(input,'b.txt');reset(input);
readln(l,n,m);
for i:=1 to n do
readln(a[i]);
a[0]:=0;a[n+1]:=l;
left:=0;
right:=l;
while left+1<right do
begin
mid:=(left+right)div 2;
if not tri(mid) then right:=mid
else left:=mid;
end;
writeln(left);close(input);
end.

同过noip数据过不了vijos数据，vijos数据真心良心。

嗯，我决定精简代码，去掉读入优化......
```
#include <bits/stdc++.h>
using namespace std;
int L, N, M;
int s[50005];

int main() {
scanf("%d%d%d",&L,&N,&M);
s[0] = 0;
for(int i=1; i<=N; i++) scanf("%d", &s[i]);
s[N+1] = L;
int l = 1, r = L;
while(l <= r) {
int mid = (l + r) >> 1;
int m = 0, pre = 0;
for(int i=1; i<=(N+1); i++)
if(s[i] - s[pre] < mid) m++;
else pre = i;
if(m <= M) l = mid+1;
else r = mid-1;
}
printf("%d\n", r);
return 0;
}
```

二分答案，O(n)判断解。
总复杂度O(nlogn)。
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int L, N, M;
int s[50005];

int main() {
L=read(); N=read(); M=read();
s[0] = 0;
for(int i=1; i<=N; i++) s[i] = read();
s[N+1] = L;
int l = 1, r = L;
while(l <= r) {
int mid = (l + r) >> 1;
int m = 0, pre = 0;
for(int i=1; i<=(N+1); i++)
if(s[i] - s[pre] < mid) m++;
else pre = i;
if(m <= M) l = mid+1;
else r = mid-1;
}
printf("%d\n", r);
return 0;
}
```

先反向判断到最后一个不用拿走的点，再正向判断
c++
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
int i,j,m,n,l,p,q,dis[50002],disn,movd;
bool can(int mid)
{
i=n;
while(l-dis[i]<mid)
{
i--;
movd++;
}
int end=i;
int st=0;
for(i=1;i<=end;i++)
{
if(dis[i]-st<mid)movd++;
else st=dis[i];
}
if(movd<=m)return true;
return false;
}
int main()
{
scanf("%d%d%d",&l,&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&dis[i]);
}
int le=1;int ri=l;
while(le<ri)
{
int mid=(ri+le+1)/2;
movd=0;
if(can(mid))le=mid;
else ri=mid-1;
}
cout<<le;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <climits>
using namespace std;

#define MAXN 50005
#define MAXM 50005
int L, N, M;
int D[MAXN];
int Ans;

bool Check(const int &dist)
{
int cnt = 0;
int LastPos = 0;
for(int i = 1; i <= N+1; i++)
{
if(D[i]-LastPos < dist) cnt++;
else LastPos = D[i];
if(cnt > M) return 0;
}
return 1;
}

int main()
{
cin >> L >> N >> M;
int l = INT_MAX;
int r = L/(N-M);
for(int i = 1; i <= N; i++)
{
scanf("%d", D+i);
}
sort(D+1, D+N+1);
D[N+1] = L;
//for(int i = 1; i <= N+1; i++)cout<<D[i]<<' ';
// cout<<endl;
for(int i = 1; i <= N+1; i++) l = min(l, D[i]-D[i-1]);
while(1)
{
//cout<<l<<' '<<r<<endl;
int div = l + r >> 1;
if(Check(div)) l = div;
else r = div;
if(l+1 == r )
{
Ans = l;
if(Check(r)) Ans = r;
break;
}
}
cout << Ans << endl;
return 0;
}

唉，经典的二分，边界要好好处理一下，不然会炸。
不过noip的数据竟然可以骗边界……
```c++
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

vector<int> stones;
int l,n,m;
int s=2e9,b;

bool is_ok(int x)
{
int flag=0;
int remove=0;
for(int i=0;i<=n;i++)
{
flag=i;
for(int j=i+1;j<=n;j++)
{
if(stones[j]-stones[i]>=x) {i=j-1;break;}
remove++;
if(j==n) {i=j;}
}
}
if(flag&&l-stones[flag]<x) remove++;
return remove<=m;
}

int main()
{
/*freopen("in","r",stdin);*/
scanf("%d%d%d",&l,&n,&m);
stones.push_back(0);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
s = min(k-stones[i-1],s);
stones.push_back(k);
}
s = min(l-stones[stones.size()-1],s);
b = l;
while(s<b)
{
int middle=s+(b-s+1)/2;
if(is_ok(middle)) s=middle;
else b=middle-1;
}

printf("%d\n",s);
return 0;
}
```

#include<cstdio>
#include<cmath>
int d[51000],L,N,M;
int pd(int m)
{
    int ans=0;
    int l=1,r=N,t;
    while(d[l]-0<m&&l<=r)l++,ans++;
    while(L-d[r]<m&&r>=l)r--,ans++;
    while(l<r)
    {
        for(t=l+1;d[t]-d[l]<m;t++)
        {
            ans++;
            if(t+1>r)return ans;
        }
        l=t;
    }
    return ans;
}
int main()
{
    scanf("%d%d%d",&L,&N,&M);
    for(int i=1;i<=N;i++)
        scanf("%d",&d[i]);
    int l,r,m;
    l=0;
    r=1000000000;
    while(l<r)
    {
        m=ceil((l+r)/2.0);
        if(pd(m)<=M)
            l=m;
        else r=m-1;
    }
    printf("%d",l);
    return 0;
}

#include<stdio.h>
int line[55555]={0};
int m,n;
int ok(int a)
{
int i,head=0,count=0;
for(i=1;i<=n;i++)
{
if(line[i]-head<a) count++;
else head=line[i];
}
if(count<=m) return 1;
else return 0;
}
int main()
{
int i,j,s,ans,head,tail,count=0;
scanf("%d%d%d",&s,&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&line[i]);
line[n+1]=s;

head=1;tail=s;
while(head<=tail)
{
if(ok((head+tail)/2)==1)
head=(head+tail)/2+1;
else tail=(head+tail)/2-1;
ans=(head+tail)/2;
}
printf("%d",ans);
return 0;
}
C的，用noi数据100分
用vijos60分.....简直了。。【接招吧】，南小鸟精神污染！！！！