AOJ 0563: Walking Santa
問題
を満たすx, y, v を求める
解法
maxの項が存在しない場合は、各軸で考えて、中央値を選べば良く、Nが偶数のときは、中央の2つの値の間の値であればどれでもよい。Nが奇数のときは一意に定まる。
maxの項が存在する場合の解は、上の問題の解のどれかであり、端点だけ調べれば良い。
計算量は、O(NlogN) (O(N)にもできる)
コード
#include <cstdio> #include <vector> #include <map> #include <algorithm> using namespace std; typedef long long ll; typedef pair<ll, ll> P; int main(){ ll h, w, n; scanf("%ld%ld%ld",&h,&w,&n); vector<ll> x(n),y(n); vector<P> p(n); for(int i = 0; i < n; i++){ scanf("%ld%ld",&x[i],&y[i]); p[i] = P(x[i], y[i]); } sort(x.begin(), x.end()); sort(y.begin(), y.end()); ll rx, ry, rv = -1; for(int i = 0; i < 4; i++){ ll ax = x[(n-1+i/2)/2], ay = y[(n-1+i%2)/2]; ll mx = 0; for(int j = 0; j < n; j++) mx = max(mx, abs(ax-p[j].first)+abs(ay-p[j].second)); if(rv<mx){ rx = ax; ry = ay; rv = mx; } } ll res = -rv; for(int i = 0; i < n; i++) res += 2*(abs(rx-x[i])+abs(ry-y[i])); printf("%ld\n%ld %ld\n", res, rx, ry); return 0; }