結果
問題 | 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;}