Time Limit: 5 Sec Memory Limit: 162 MB
Description
营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值 当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。
Input
第一行为正整数 ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i天公司的营业额。
Output
输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。
Sample Input
6
5
1
2
5
4
6
5
1
2
5
4
6
Sample Output
12
HINT
结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
继续学习红黑树的结点删除QaQ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | #include <cstdio>#include <cstdlib>using namespace std;struct node{ bool Color; //True: Red False: Black int Key; node* p; node* left, * right;};int ans = 0;node* Root;//根节点node* NIL;//空节点#ifdef _DEBUGtemplate<typename type="">constexpr auto min(Type a, Type b) { if (a < b)return a; else return b; }#else#define min(a,b) ((a)<(b)?(a):(b))#endif // _DEBUGvoid Init(){ NIL = new node; //定义空哨兵节点（叶子结点和根节点的父节点） NIL->Color = false; NIL->left = NIL->right = NULL; NIL->Key = 0; Root = NULL;}int Insert(node* pnt, node *z) //插入元素 返回值为与树内结点差绝对值最小值{ if (pnt == NULL) //空红黑树 p为根节点 { Root = z; z->p = NIL; return z->Key; } int temp;//临时变量 用于记录下一层Insert返回值 if (z->Key < pnt->Key)//z将被加入左子树豪华午餐 { if (pnt->left == NIL) { pnt->left = z; z->p = pnt; return pnt->Key - z->Key; } else { temp = Insert(pnt->left, z); return min(temp, pnt->Key - z->Key); } } else //z将被加入右子树奢华晚餐 { if (pnt->right == NIL) { pnt->right = z; z->p = pnt; return z->Key - pnt->Key; } else { temp = Insert(pnt->right, z); return min(temp, z->Key - pnt->Key); } }}void Shift_L(node* pnt)//树左旋{ node* temp = pnt->right; pnt->right = temp->left; temp->left->p = pnt; temp->p = pnt->p; if (pnt->p->left == pnt)pnt->p->left = temp; else pnt->p->right = temp; pnt->p = temp; temp->left = pnt; if (pnt == Root)Root = temp;}void Shift_R(node* pnt)//树右旋{ node* temp = pnt->left; pnt->left = temp->right; temp->right->p = pnt; temp->p = pnt->p; if (pnt->p->left == pnt)pnt->p->left = temp; else pnt->p->right = temp; pnt->p = temp; temp->right = pnt; if (pnt == Root)Root = temp;}void Fix_up(node* z){ while (z->p->Color)//z的父节点为红色（z也为红色）不符合红黑树定义 { if (z->p->p->left == z->p)//z的父节点在祖父节点的左子树上 { if (z->p->p->right->Color)//叔节点为红色 { z->p->p->Color = true; z->p->p->left->Color = z->p->p->right->Color = false; z = z->p->p; } else { if (z == z->p->right)//z在右节点上，左旋一下 { z = z->p; Shift_L(z); } z->p->Color = false; z->p->p->Color = true; Shift_R(z->p->p); } } else //z的父节点在z的祖父节点右子树上 所有操作左右相反即可 { if (z->p->p->left->Color)//叔节点为红色 { z->p->p->Color = true; z->p->p->left->Color = z->p->p->right->Color = false; z = z->p->p; } else { if (z == z->p->left)//z在左节点上，右旋一下 { z = z->p; Shift_R(z); } z->p->Color = false; z->p->p->Color = true; Shift_L(z->p->p); } } } Root->Color = false;}void TreeOut(node* Pos){ if (Pos == NIL)return; printf("%d %d l:%d r:%d p:%d\n", Pos->Key, Pos->Color, Pos->left->Key, Pos->right->Key, Pos->p->Key); TreeOut(Pos->left); TreeOut(Pos->right);}int n, x;int main(){ Init(); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &x); node* z = new node; z->Key = x; z->left = z->right = NIL; z->Color = true; ans += Insert(Root, z); Fix_up(z);#ifdef _DEBUG printf("-------------%d------------\n", x); TreeOut(Root);#endif // _DEBUG } printf("%d\n", ans); return 0;}</typename></cstdlib></cstdio> |
