結果
問題 | No.275 中央値を求めよ |
ユーザー |
|
提出日時 | 2016-03-11 03:32:48 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,000 ms |
コード長 | 1,166 bytes |
コンパイル時間 | 685 ms |
コンパイル使用メモリ | 70,844 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 23:43:57 |
合計ジャッジ時間 | 1,794 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream> #include <memory> class Bin_tree{ public: Bin_tree(const int &v) :left{ nullptr }, right{ nullptr }, factor_size{ 1 }, val{ v } {}; void insert(const int &v) { ++factor_size; if (v > val) { if (right) { right->insert(v); } else { right = std::make_shared<Bin_tree>(Bin_tree(v)); } } else { if (left) { left->insert(v); } else { left = std::make_shared<Bin_tree>(Bin_tree(v)); } } } double median() const { if ((factor_size & 1) == 0) { return (get_nth_val(factor_size >> 1) + get_nth_val((factor_size >> 1) + 1)) / 2.0; } else { return get_nth_val((factor_size >> 1) + 1); } } private: std::shared_ptr<Bin_tree> left, right; int factor_size, val; int get_nth_val(const int &n) const { int l = (left) ? left->factor_size : 0; if (n == l + 1) { return val; } else if (n <= l) { return left->get_nth_val(n); } else { return right->get_nth_val(n - l - 1); } } }; int main() { int n, a; std::cin >> n >> a; Bin_tree root(a); for (; n > 1; --n) { int an; std::cin >> an; root.insert(an); } std::cout << root.median() << std::endl; return 0; }