宝应人网站论坛,wordpress自定义后台菜单,网站宝搭建网站环境,网站产品页面题目大意 给出一个长度为N的非负整数序列A[i]#xff0c;对于所有1 ≤ k ≤ (N 1) / 2#xff0c;输出A[1], A[3], …, A[2k - 1]的中位数。即前1#xff0c;3#xff0c;5#xff0c;……个数的中位数。 题解 要找到中位数我们需要的序列是单调不减的#xff0c;故可以…题目大意 给出一个长度为N的非负整数序列A[i]对于所有1 ≤ k ≤ (N 1) / 2输出A[1], A[3], …, A[2k - 1]的中位数。即前135……个数的中位数。 题解 要找到中位数我们需要的序列是单调不减的故可以用二叉平衡树解决。 #include cstdio
#include cstring
#include algorithm
using namespace std;const int MAX_NODE 100010;struct SplayTree
{
private:struct Node{Node *LeftSon, *RightSon, *Father;int Key, Size, Count;Node(Node *fa, int key) : Father(fa), LeftSon(NULL), RightSon(NULL), Key(key), Size(1), Count(1){}bool IsLeftSon(){return Father-LeftSon this;}void Refresh(){Size (LeftSon ? LeftSon-Size : 0) (RightSon ? RightSon-Size : 0) Count;}bool IsRoot(){return Father NULL || (Father-LeftSon ! this Father-RightSon ! this);}}*Root;void Rotate(Node *cur){Node *gfa cur-Father-Father;Node **gfaSon gfa ? (cur-Father-IsLeftSon() ? gfa-LeftSon : gfa-RightSon) : Root;Node **faSon cur-IsLeftSon() ? cur-Father-LeftSon : cur-Father-RightSon;Node **curSon cur-IsLeftSon() ? cur-RightSon : cur-LeftSon;*faSon *curSon;if (*faSon)(*faSon)-Father cur-Father;*curSon cur-Father;(*curSon)-Father cur;*gfaSon cur;(*gfaSon)-Father gfa;(*curSon)-Refresh();cur-Refresh();}void PushDown() {}void Splay(Node *cur){PushDown();while (cur-Father){if (!cur-Father-IsRoot())Rotate(cur-Father-IsLeftSon() cur-IsLeftSon() ? cur-Father : cur);Rotate(cur);}}int GetKeyByRank(Node *cur, int rank){int rootSize, leftSize (cur-LeftSon ? cur-LeftSon-Size : 0);if (rank leftSize)return GetKeyByRank(cur-LeftSon, rank);else if (rank (rootSize leftSize cur-Count))return cur-Key;elsereturn GetKeyByRank(cur-RightSon, rank - rootSize);}public:void Insert(int key){Node **cur Root, *fa NULL;while (*cur){fa *cur;if (key (*cur)-Key){(*cur)-Count;Splay(*cur);return;}else if (key (*cur)-Key)cur (*cur)-LeftSon;else if (key (*cur)-Key)cur (*cur)-RightSon;}*cur new Node(fa, key);Splay(*cur);}int GetKeyByRank(int rank){return GetKeyByRank(Root, rank);}
}g;int main()
{static int A[MAX_NODE];int n;scanf(%d, n);for (int i 1; i n; i)scanf(%d, A i);for (int i 1; i n; i 2){g.Insert(A[i]);printf(%d\n, g.GetKeyByRank(i / 2 1));g.Insert(A[i 1]);}return 0;
} 转载于:https://www.cnblogs.com/headboy2002/p/9028748.html
