题目链接:P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意就不说了,请看原题。
这道题我在很久之前就A了,昨天朋友问起发现自己还写错了几次,实在惭愧,今天记录一下这个思路。
思路
首先,如果已知撤走的石头,想要求最短距离,是不容易的,但是如果已知最短距离,求“一定要至少撤走多少个石头”可以通过遍历一遍,O(N)的复杂度算出来。
再发现,最短距离和撤走的石头数目是成正相关的,撤走的石头越多,最短的跳跃距离不变或越多,于是可以想到二分法。二分的是最短距离,然后通过最短距离求到至少要撤走多少个石头。
此时去找临界条件,即最短距离再 + 1就会导致撤走的石头也要 + 1这个临界条件。
即check(l) = M,check(r) = M + 1,此时的 l 就是最大的“最短跳跃距离”。
听起来蛮怪的,最大的最短距离,但是确实是这么回事。
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 5e4 + 10; int L, N, M, d[maxn]; int check(int k)//当距离固定为k时,可以撤走多少个石头 { int dist = 0, res = 0; for(int i = 1;i <= N; ++ i) { //如果两点之间距离小于k,即不满足最短距离为k的条件 if(d[i] - dist < k)res ++; else dist = d[i]; } return res; } signed main() { cin >> L >> N >> M; for(int i = 1;i <= N; ++ i)cin >> d[i]; d[++ N] = L;//将终点也存下来,作为第N个点 int l = 0,r = L + 1; while(l + 1 != r) { //撤走的石头个数和最近跳跃距离成正相关 int mid = l + ((r - l) >> 1); if(check(mid) <= M)l = mid; else r = mid; } cout << l << '\n'; return 0; }
Comments NOTHING