对外宣传网站建设方案,国外网站赏析,china cd wordpress,scratch编程免费下载1588: [HNOI2002]营业额统计 Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 17931 Solved: 7391[Submit][Status][Discuss]Description 营业额统计 Tiger最近被公司升任为营业部经理#xff0c;他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 T… 1588: [HNOI2002]营业额统计 Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 17931 Solved: 7391[Submit][Status][Discuss] Description 营业额统计 Tiger最近被公司升任为营业部经理他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日大减价或者是其他情况的时候营业额会出现一定的波动当然一定的波动是能够接受的但是在某些时候营业额突变得很高或是很低这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况 该天的最小波动值 当最小波动值越大时就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。 输入输出要求 Input 第一行为正整数 表示该公司从成立一直到现在的天数接下来的n行每行有一个整数(有可能有负数) 表示第i 天公司的营业额。 天数n32767, 每天的营业额ai 1,000,000。 最后结果T2^31 Output 输出文件仅有一个正整数即Sigma(每天最小的波动值) 。结果小于2^31 。 Sample Input 6 5 1 2 5 4 6 Sample Output 12 HINT 结果说明5|1-5||2-1||5-5||4-5||6-5|54101112 该题数据bug已修复.----2016.5.15 分析splay裸题每次找前驱和后继找前驱的方法是在左子树中找最大的数一直往右跳后继就是在右子树中找最小的数往左跳.需要注意的是每次插入完一个数都要将它翻到上面去.并且要更新根节点 #include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int maxn 40010;struct node
{int fa,left,right,v;
}e[maxn];int n,ans,Time,t,root 1;
bool flag true;void turnr(int x)
{int y e[x].fa;int z e[y].fa;e[y].left e[x].right;if (e[x].right ! -1)e[e[x].right].fa y;e[x].fa z;if (z ! -1){if (e[z].left y)e[z].left x;elsee[z].right x;}e[x].right y;e[y].fa x;
}void turnl(int x)
{int y e[x].fa;int z e[y].fa;e[y].right e[x].left;if (e[x].left ! -1)e[e[x].left].fa y;e[x].fa z;if (z ! -1){if (e[z].left y)e[z].left x;elsee[z].right x;}e[x].left y;e[y].fa x;
}void splay(int x)
{while (e[x].fa ! -1){int y e[x].fa;int z e[y].fa;if (z -1){if (x e[y].left)turnr(x);elseturnl(x);}else{if (e[z].left y e[y].left x){turnr(y);turnr(x);}else{if (e[z].right y e[y].right x){turnl(y);turnl(x);}else{if (e[z].left y e[y].right x){turnl(x);turnr(x);}else{turnr(x);turnl(x);}}}}}root x;
}void insert(int x,int y)
{if (x e[y].v){flag false;splay(y);return;}if (x e[y].v){if (e[y].left -1){e[y].left Time;e[Time].left e[Time].right -1;e[Time].fa y;e[Time].v x;}elseinsert(x,e[y].left);}else{if (e[y].right -1){e[y].right Time;e[Time].left e[Time].right -1;e[Time].fa y;e[Time].v x;}elseinsert(x,e[y].right);}
}int findl(int x)
{int y e[x].left;if (y -1)return y;while (e[y].right ! -1)y e[y].right;return y;
}int findr(int x)
{int y e[x].right;if (y -1)return y;while (e[y].left ! -1)y e[y].left;return y;
}void solve(int x)
{flag true;insert(x,root);if (!flag)return;splay(Time);int p findl(Time),q findr(Time);int temp 0x7fffffff;if (p ! -1)temp min(temp,abs(x - e[p].v));if (q ! -1)temp min(temp,abs(x - e[q].v));if (temp ! 0x7fffffff)ans temp;
}int main()
{scanf(%d,n);scanf(%d,t);ans t;e[Time].fa -1;e[Time].left -1;e[Time].right -1;e[Time].v t;for (int i 2; i n; i){scanf(%d,t);solve(t);}printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/zbtrs/p/8231725.html
