あいさつまわり [パソコン甲子園2020 予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0430

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0430/review/5787700/hamayanhamayan/C++14

今回の問題はどういう順番で家を訪ねていくかというのを考えていくものであるが、
全組合せを見ていく方法は実装も大変だし、計算量も間に合わないので、うまくやる必要がある。
今回は、貪欲法をつかって解いていこう。

貪欲法

貪欲法とは一定のルールに従って問題を解くことで最適解を得ようとする方針である。
一直線上に

1   2   x0     3      4  

みたいに位置取りがなされている場合にどうやって回るのが最適っぽいかを考えてみる。
左右に連続的な移動しかできないということと、末端に必ず移動しないといけないということを考えると、
x0から左端の1に向かってそれから右端の4に向かうか、x0から右端の4に向かってそれから左端の1に向かう
のが最適となりそうである。

よって最適解は、以下の2操作のうち、移動距離が小さい方になる。

x0 → 左端 → 右端
x0 → 右端 → 左端

まずは、左端mi, 右端maを計算して、2点間の距離は差の絶対値となるので、abs関数をうまく使いながら
貪欲法で最適解を求めていこう。

int N, x0, x[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> x0;
    rep(i, 0, N) cin >> x[i];

    int mi = inf;
    rep(i, 0, N) chmin(mi, x[i]);

    int ma = -1;
    rep(i, 0, N) chmax(ma, x[i]);

    int ans = min(abs(x0 - mi) + abs(mi - ma), abs(x0 - ma) + abs(ma - mi));
    cout << ans << endl;
}