本文主要是介绍NOIP2015 跳石头，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题： 传送门
题意： 从N个石头（不含起点和终点）中去掉至多M块石头，使得从起点跳到终点的最小步长最大化
思路： 用二分法从0 ~ L枚举最后的答案，如果可以在移动至多M块石头的情况下达成此步长，则继续往(l+r)/2 ~ L搜索，否则就往l ~ (l+r)/2搜索一直到l > r 为止
注意： 把起点和终点也加进去，方便计算第一个石头到起点的距离和终点到最后一个石头的距离
Code：
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>using namespace std;int l, m, n;
int stone[60007];bool check (int x) {int now = 0;int cnt = 0;for (int i=1;i<=n+1;i++) {if (stone[i] - stone[now] < x) {cnt++;} else {now = i;}}return cnt <= m;
}
int search (int l, int r) {int ans = 0;int mid;while (l <= r ) {mid = (l+r) / 2;if (check(mid)) {ans = mid;l = mid + 1;} else {r = mid - 1;}}return ans;
}
int main()
{ios::sync_with_stdio(false);cin>>l>>n>>m;for (int i=1;i<=n;i++) {cin>>stone[i];}stone[n+1] = l;cout<<search(0, stone[n+1])<<endl;return 0;
}
这篇关于NOIP2015 跳石头的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
