当前位置：首页 > news >正文

【每日一题】【平衡树】【__gnu_pbds :: tree】小红的中位数牛客周赛 Round 29 D题 C++

news 来源：原创 2024/9/20 14:32:58

牛客周赛 Round 29 D题

小红的中位数

题目背景

牛客周赛 Round 29

题目描述

样例 #1

样例输入 #1

4
2 5 8 1

样例输出 #1

5.0
2.0
2.0
5.0

样例 #2

样例输入 #2

3
1 2 3

样例输出 #2

2.5
2.0
1.5

做题思路

本题提供Policy-Based Data Structures中的平衡树做法。

详细信息请见:平衡树

通过描述：如果想要存储多个相同的 Key 元素，则需要使用类似于 std::pair 和 struct 的方法

所以 Key 可以使用 std::pair

使用从小到大的默认排序，和红黑树为底层数据结构类型(最优)。

更新节点的策略的选择：因为要用find_by_order 方法，需要使用 tree_order_statistics_node_update。

如果是原本是奇数个数的数组，去掉一个后为偶数，找到中间两个数字即可得到中位数。
反之是奇数，找到最中间的数字(中位数)。

find_by_order(x)：返回 Cmp_Fn 比较的排名所对应元素的迭代器。

利用find_by_order(n/2)即可找到中间位置的数字

trr.erase({a[i],i}); // 取出第i个数字
printf("%.1f\n",((n&1)  ? ((double)trr.find_by_order(m)->first + (double)trr.find_by_order(m-1)->first)/2.0 : (double)trr.find_by_order(m-1)->first )); //获取目前数组的中位数
trr.insert({a[i],i});//再把第i个数字放入

代码

#include <iostream>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>#define int long long
#define For(a,b) for(int i = (a) ; i<= (b) ; i++)
using namespace  std;const int N = 2e7+10;__gnu_pbds ::tree<pair<int, int>, __gnu_pbds::null_type, less<pair<int, int> >,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>trr;
int n , m;
int a[N];
void solve(){cin >> n;For(0,n-1){cin >> a[i];trr.insert({a[i],i});}m = n/2;for(int i=0;i<n;i++){trr.erase({a[i],i});printf("%.1f\n",((n&1)  ? ((double)trr.find_by_order(m)->first + (double)trr.find_by_order(m-1)->first)/2.0 : (double)trr.find_by_order(m-1)->first ));trr.insert({a[i],i});}
}
signed main(){int _=1;//cin >> _;while(_--)solve();return 0;
}