公式

F - 試験の結果/Test Result 解説 by MMNMM


多くの言語では、ソートをする際の比較関数を与えることができます。

整数の比較によるソートしかできない言語では、十分大きな整数 \(X,Y\) を用いて \(((E _ i+M _ i)\times X+M _ i)\times Y+i\) をソートすることなどで求めるソートを実現することができます(値から対応する生徒の番号を求めるのは \(Y\) で割った余りを求めればよいでしょう)。

実装例は以下のようになります。 C++ では std::sort 関数などに比較関数を与えることができます。

#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <algorithm>
#include <tuple>

int main() {
    unsigned N;
    std::cin >> N;

    std::vector<std::pair<unsigned, unsigned>> exam_result(N);
    for(auto&& [E, M] : exam_result)
        std::cin >> E >> M;

    std::vector<unsigned> student_id(N);
    std::iota(std::begin(student_id), std::end(student_id), 0U);
    std::ranges::sort(student_id, std::greater<>{}, [&exam_result](auto i){
        const auto& [E, M]{exam_result[i]};
        return std::make_tuple(E + M, M, i);
    });

    for (const auto id : student_id)
        std::cout << id + 1 << " ";
    std::cout << std::endl;
    return 0;
}

投稿日時:
最終更新: