Square869120 B-AtCoder Markets
問題概要
人の買い物客がそれぞれマスにある品物とマスにある品物を購入する。入り口と出口を設置する時、買い物客は次のように行動する。
- まず入り口からスタートし、マスを経由して、出口でゴールする。
隣り合ったマス目の移動に秒かかる時、最適に入り口と出口を定めた時の「全ての買い物客の移動時間の合計」の最小値を求めよ。
制約
考察
最短となるスタートとゴールの組み合わせは、それぞれの中央値になる。
したがって、中央値を求め、それらをそれぞれ start, goal とする時、との距離をそれぞれ計算してあげると良い。
それぞれの距離は、となる。
answer.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
int N; cin >> N;
vector<long long> a(N), b(N);
long long start, goal;
for(int i = 0; i < N; i++) {
cin >> a[i] >> b[i];
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
start = a[N/2], goal = b[N/2];
long long ans=0;
for(int i = 0; i < N; i++) {
ans += abs(a[i] - b[i]);
ans += abs(start-a[i]);
ans += abs(goal-b[i]);
}
cout << ans << endl;
return 0;
}