PKU3258 River Hopscotch
蟻本の練習問題。
岩の位置をソートして二分探索
#include <cstdio> #include <algorithm> using namespace std; int l, m, n; int rock[50000]; bool C(int d){ int last = 0; while(rock[last] < d){ last++; if(last == n) return false; } for(int i = 1; i < n - m; i++){ int crt = last + 1; while(crt < n && rock[crt] - rock[last] < d){ crt++; } if(crt == n) return false; if(l - rock[crt] < d) return false; last = crt; } return true; } int main(){ scanf("%d %d %d", &l, &n, &m); for(int i = 0; i < n; i++){ scanf("%d", &rock[i]); } sort(rock, rock + n); int lb = 0; int ub = l + 1; while(ub - lb > 1){ int mid = (ub + lb) / 2; if(C(mid)) lb = mid; else ub = mid; } printf("%d\n", lb); return 0; }