吸氧大法好
by wxy_god @ 2018-10-16 21:46:18
给您一份本蒟蒻的代码~希望有用
```cpp
#include<bits/stdc++.h>//p2678跳石头
using namespace std;
const int N=50010;
long long d,n,m,i,l,r;
long long s[N];
bool check(int h)
{
int sum=0,i=1,now=0;
while(i<=n)
{
if(s[i]-s[now]<h)
sum++;
else
now=i;
i++;
}
if(sum<=m)
return 1;
else
return 0;
}
int main()
{
cin>>d>>n>>m;
for(i=1;i<=n;i++)
cin>>s[i];
if(n==0)
{
cout<<d<<endl;
return 0;
}
s[0]=0;s[n+1]=d;
l=0;r=d;
while(l+1<r)
{
int m=(l+r)/2;
if(check(m)==1)
l=m;
else
r=m;
}
cout<<l<<endl;
return 0;
}
```
by deleted @ 2018-10-16 21:47:20
@[Derrick787](/space/show?uid=107355)
您的代码思路比较清晰，简单易懂，让我学到了一些技巧，感谢。
by zhengdihan @ 2018-10-16 21:56:35
@[我是一个垃圾](/space/show?uid=89396) are you sure？
by zhengdihan @ 2018-10-16 21:56:55
@[zhengdihan](/space/show?uid=108832) 为什么不呢？
by wxy_god @ 2018-10-16 21:58:47
@[我是一个垃圾](/space/show?uid=89396) 不信你去试一试
by zhengdihan @ 2018-10-16 22:00:04
@[zhengdihan](/space/show?uid=108832) 好吧。。。
by wxy_god @ 2018-10-16 22:01:24
@[zhengdihan](/space/show?uid=108832) 竟然没发现是自己做过的题 好像跟楼上的代码有点像
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int L, n, m, d[50008];
inline int read(){
int ret = 0; char c;
while(!isdigit(c = getchar())) continue;
ret = c - '0';
while(isdigit(c = getchar())) ret = ret * 10 + c - '0';
return ret;
}
inline bool check(int x){
int pos = 0, cnt = 0;
for(int i=1 ; i<=n ; i++){
if(d[i] - pos < x)
++cnt;
else
pos = d[i];
}
if(L - pos < x) return false;
else return cnt<=m;
}
int main () {
L = read(); n = read(); m = read();
for(int i = 1 ; i <= n ; i ++ )
d[i] = read();
sort(d + 1, d + n + 1);
int l = 0, r = L + 1;
while(l < r)
{
int mid = (l + r) / 2;
if(check(mid)) l = mid + 1;
else r = mid;
}
printf("%d", l - 1);
return 0;
}
```
by wxy_god @ 2018-10-16 22:03:06
@[我是一个垃圾](/space/show?uid=89396) 对
by zhengdihan @ 2018-10-18 20:03:24