闇討ち [yukicoder 1028]

https://yukicoder.me/problems/no/1028

前提知識

• 三分探索

解説

https://yukicoder.me/submissions/466456

難しい問題。三分探索で解く。

三分探索で解くというのに気づくのが一番難しい。
（二分探索系は大体そう）
方針は「各社員の家について、(1,1)～(N,1)のどこで襲撃するのが最適かを高速に見つける」。
(1,1)～(N,1)のそれぞれで襲撃にかかる移動回数を計算してみると、凸性を持つことが分かる。
よって、どこが最適であるかは、三分探索で求めることが可能。

あとは、それぞれの社員について、最適な移動回数の総和を求めれば答え。
計算量O(N^2logN)

int N, A[1010][1010];
//---------------------------------------------------------------------------------------------------
vector<pair<int, int>> houses[1010];
int employee;
int f(int x) {
    int tot = 0;
    fore(p, houses[employee]) tot += max(abs(x - p.first), p.second);
    return tot;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(x, 0, N) rep(y, 0, N) cin >> A[x][y];
    rep(x, 0, N) rep(y, 0, N) houses[A[x][y]].push_back({ x, y });

    int ans = 0;
    rep(e, 1, N + 1) {
        employee = e;
        int optx = findMin(0, N, f);
        ans += f(optx);
    }
    cout << ans << endl;
}