陕西网站seo,6黄页网站建设,网站图片自动轮换怎么做的,淘宝网店装修【题目来源】 https://www.luogu.com.cn/problem/P2234 【题目描述】 Tiger 最近被公司升任为营业部经理#xff0c;他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger 拿出了公司的账本#xff0c;账本上记录了公司成立以来每天的营业额。分析…【题目来源】 https://www.luogu.com.cn/problem/P2234 【题目描述】 Tiger 最近被公司升任为营业部经理他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger 拿出了公司的账本账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日大减价或者是其他情况的时候营业额会出现一定的波动当然一定的波动是能够接受的但是在某些时候营业额突变得很高或是很低这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况当最小波动值越大时就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。 我们定义一天的最小波动值 min{∣该天以前某一天的营业额−该天营业额∣}。 特别地第一天的最小波动值为第一天的营业额。 【输入格式】 第一行为正整数 nn≤32767 表示该公司从成立一直到现在的天数接下来的 n 行每行有一个整数 ai∣ai∣≤10^6) 表示第 i 天公司的营业额可能存在负数。 【输出格式】 输出一个正整数即每一天最小波动值的和保证结果小于 2^31。 【输入样例】 6 5 1 2 5 4 6 【输出样例】 12 【说明/提示】 结果说明5∣1−5∣∣2−1∣∣5−5∣∣4−5∣∣6−5∣54101112 【算法分析】 ● STL set 常用函数解析 https://blog.csdn.net/hnjzsyjyj/article/details/127017796 https://blog.csdn.net/hnjzsyjyj/article/details/145528031 ● 代码逻辑解析 一初始化阶段 在集合 s 中预先插入 inf 和 -inf确保后续查找操作始终存在前驱和后继节点避免空集合导致的异常。注意此处的无穷大 inf 设为 0x3f3f3f3f不要设为 0x7f7f7f7f。这是因为0x7f7f7f7f 的缺点是容易在加法运算中溢出导致负数结果这在算法中可能引发错误。 二输入处理阶段 读取整数 n循环处理每个输入值 x。 1.当集合仅含初始边界 inf 和 -inf 时s.size() 2直接插入 x 并将 x 累加到答案 ans 中。 2. 当集合已有其他元素时 1使用 lower_bound(x) 找到第一个大于等于 x 的迭代器 it。 2若 *it ! x即 x 不存在于集合中计算 x 与 *it后继和 *--t前驱的最小差值累加到 ans。 3插入 x 到集合中。 三输出结果 最终输出累加的最小差值总和 ans。 ● 计算过程详析 1.输入 5 时 → 集合初始只有两个边界 → ans5 → 插入 5 2.输入 1 时 → 前驱 -inf后继 5 → 最小差值 4 → ans4 → 插入 1 3.输入 2 时 → 前驱 1后继 5 → 最小差值1 → ans1 → 插入 2 4.输入 5 时 → 已存在不处理 5.输入 4 时 → 前驱 2后继 5 → 最小差值 1 → ans1 → 插入 4 6.输入 6 时 → 前驱 5后继 inf → 最小差值 1 → ans1 → 插入 6 累计总和5411112 ● 适用场景 该算法适用于需要动态维护有序序列并在每次插入时快速计算与相邻元素的最小差值的场景如实时数据流分析或特定竞赛题目。 【算法代码】
#include bits/stdc.h
using namespace std;const int inf0x3f3f3f3f;
setint s;
setint::iterator it,t;
int x,ans;
int n;int main() {s.insert(inf);s.insert(-inf);cinn;while(n--) {cinx;if(s.size()2) {s.insert(x);ansx;} else {its.lower_bound(x);if(*it!x) {tit, t--;ansmin(abs(x-*it),abs(x-*t));s.insert(x);}}}coutansendl;return 0;
}/*
in:
6
5
1
2
5
4
6out:
12
*/ 【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/145528031 https://blog.csdn.net/hnjzsyjyj/article/details/146110033
