JOI春合宿2008Day2 cheating
適当ににぶたんすると通る
問題文読み間違って無駄に難しくしてた...
#include <cstdio> #include <algorithm> #include <climits> using namespace std; int n, m; int x[100000], y[100000]; bool C(int k){ int crt = -INT_MAX, num = 0; for(int i = 0; i < m && num <= n; i++){ if(crt + k < x[i]){ num++; crt = x[i]; } } if(num > n) return false; crt = -INT_MAX; for(int i = 0; i < m && num <= n; i++){ if(crt + k < y[i]){ num++; crt = y[i]; } } if(num > n) return false; return true; } int main(){ scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) scanf("%d %d", &x[i], &y[i]); sort(x, x + m); sort(y, y + m); int lb = -1, ub = INT_MAX; while(ub > lb + 1){ int mid = (lb + ub) / 2; if(C(mid)) ub = mid; else lb = mid; } printf("%d\n", ub); return 0; }