競プロ典型90問 014(★3) 貪欲法 - まっつーのブログ

014 - We Used to Sing a Song Together（★3）

問題

N人。家は $A_i$ にある。

学校は N校あり、 $B_j$ にある。

全員別の学校に通わせる。
学生 i の家から学校までの距離 $E_i$ , 不便さは距離の総和 $(E_1+E_2+...+E_N)$ である。
位置 u から位置 vまでの距離は $|u-v|$

不便さの最小値を求める。

解法

A,B ともにソートして、前から差の絶対値を足していくだけ。

全体計算量は $O(N\log N)$ で求められる。

所感

内容がシンプルだったのでそのままって感じだった。

コードもシンプルに書けた。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int n;
int a[100100], b[100100];
ll ans;

int main()
{
    cin >> n;
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    sort(a, a + n);
    sort(b, b + n);
    rep(i,n) ans += abs(a[i] - b[i]);
    cout << ans << endl;
    return 0;
}