网站域名中文后缀,不想花钱做网站推广,做门户网站主要技术哪一块,动漫制作专业使用的电脑题目大意 给出一个长度为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
