洛谷P2678题解

P2678虽然是黄题，但是只要想通思路，就会变得异常简单。
以下是思路《跳石头》算法思路详解.url








100分错1个点代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int L,N,M,d[50005];
bool check(int x){int cnt=0,last=0;for(int i=1;i<=N;i++){if(d[i]-last<x)cnt++;else last=d[i];}if(L-last<x)return false;return cnt<=M;
}
int main(){cin>>L>>N>>M;for(int i=1;i<=N;i++)cin>>d[i];int l=1,r=L;while(l<r){int mid=(l+r+1)>>1;if(check(mid))l=mid;else r=mid-1;}cout<<l;return 0;
}

100分AC代码：

点击查看代码

#include<iostream>
#include<algorithm>
using namespace std;
int L,N,M,d[50005];
bool check(int x){int cnt=0,last=0;for(int i=1;i<=N+1;i++){int pos=(i<=N)?d[i]:L;if(pos-last<x)cnt++;else last=pos;}return cnt<=M;
}
int main(){cin>>L>>N>>M;for(int i=1;i<=N;i++)cin>>d[i];int l=1,r=L;while(l<r){int mid=(l+r+1)>>1;if(check(mid))l=mid;else r=mid-1;}cout<<l;return 0;
}

我敢保证，这绝对是最优解！
欢迎借鉴~~