题解 | #跳石头#

通过二分枚举判断最小距离的最大值，判断达到该值要移除的石头个数与要求移除石头个数作比较，进而判断距离的增减

#include<bits/stdc++.h> #include<unordered_map> #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll;

const int N = 500010; int a[N]; int n, m, k;

bool check(int len) { int last = 0, cnt = 0; //通过移除石头保证两个石头间的距离都大于等于len距离的条件需要移除石头个数 for (int i = 1; i <= m; i++) { if (a[i] - a[last] < len) cnt++; else last = i; }

//判断移除的石头个数是否小于要求的个数
if (cnt <= k) 
	return true;
else 
	return false;

}

void solve() { cin >> n >> m >> k; for (int i = 1; i <= m; i++) cin >> a[i]; //将终点距离放进数组 a[++m] = n;

int l = 1, r = n;
while (l < r) {
	int mid =  (r + l + 1) >> 1;
	//判断mid是否是最小距离的最大值
	if (check(mid))
		//是这向上判断一下
		l = mid ;
	else
		//不是这向下判断
		r = mid - 1;
}
cout << l << endl;

}

int main() { IOS; int _ = 1; //cin >> ; while (--) { solve(); } return 0; }