二分探索にしか見えない。。
思った以上に簡単だった。
汚いソースですが。
#include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define pb push_back using namespace std; int main(){ int n, m, a, b, ld = 0, rd = 1000000000, d, nx, ny, xi, yi; vector<int> x, y; scanf("%d%d",&n,&m); rep(i,m){ scanf("%d%d",&a,&b); x.pb(a); y.pb(b); } sort(x.begin(), x.end()); sort(y.begin(), y.end()); while(ld < rd){ d = (ld+rd)/2; nx = 0; ny = 0; xi = 1; yi = 1; for(int j = 1; j < m; j++){ nx += x[j] - x[j-1]; ny += y[j] - y[j-1]; if(nx > d){xi++; nx = 0;} if(ny > d){yi++; ny = 0;} } if(xi + yi > n) ld = d+1; else rd = d; } printf("%d\n", ld); return 0; }