【競プロ問題解説】Vito’s Family (CPE04106,uva10041)by C++

競プロ問題解説
問題文
問題文の解説
サンプルコード
コードの解説

競プロ問題解説

今日は台湾の競技プログラミングの問題解説をしていきます。
問題文は英語ですが、問題自体は簡単なやつなので初心者でも気軽に解けると思います。

問題文

問題文はOnline Judgeというサイトで確認できます。

Online Judge

問題文の解説

彼はすべての親戚を訪問する予定なので、彼らに近い家を見つけようとしています。全ての親戚への総距離の最小値を求めてください。

上の画像はインプット、アウトプットの記載です。

最短距離は中央値を求めることで最適化された合計を求めることができます。
そのため今回のコードでは中央値を求める能力が求められます。

サンプルコード

GitHub上にサンプルコード載せております

cpe/一顆星/uva10041/01.cpp at main · mintson0517/cpe

Contribute to mintson0517/cpe development by creating an account on GitHub.

コードの解説

#include <iostream>
#include <vector>
#include <algorithm>

ヘッダーファイルではこちらの三つを使用します。
標準出力(iostream)、配列(vector)、小から大へ順序変(algorithm)

 int testcase; 
    cin >> testcase;

    vector<int> d(testcase, 0);

    for (int i = 0; i < testcase; ++i) {
        int r; 
        cin >> r;

        vector<int> s(r); 
        for (int j = 0; j < r; ++j) {
            cin >> s[j];
        }

テストケース、forループで親戚の数rと番号sを入力します。
番号sは動的配列としてvectorを使用しています。

動的配列の公式：vector<型> 変数名(要素数の大きさ,値)

sort(s.begin(), s.end());

これはヘッダーファイルの(algorithm)を使用しているのでこの一行だけでばらばらの順番に並んでいる番号を小から大に並べなおされました

もし大から小にする場合はrbegin,rend　反転(reverse)の形で並べられます

int mid;
        if (r % 2 == 0) { 
            mid = (s[r / 2 - 1] + s[r / 2]) / 2;
        } else { 
            mid = s[r / 2];
        }

こちらは中央値を求める際のコードです。
親戚の数が偶数と奇数では中央値を求める公式は違ってきます。

例えば：
1、2、3、4の中央値は　(2＋3)/2=2.5となります。
1、2、3の中央値は　真ん中の2になります。

for (int j = 0; j < r; ++j) {
            d[i] += abs(s[j] - mid);
}

自分の場所からの距離の差を求めるため番号-中央値(自分の住んでる所)となります。

abs は absolute value（絶対値）の略

for (int i = 0; i < testcase; ++i) {
        cout << d[i] << endl;
}

最後は答えのd[i]配列をforループですべて表示して終わります。