阜宁专业做网站域名备案官网

阜宁专业做网站,域名备案官网,给做网站公司写锦旗语,深圳网站建设分期付csp信奥赛C标准模板库STL案例应用7 set实践 题目描述 Tiger 最近被公司升任为营业部经理#xff0c;他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger 拿出了公司的账本#xff0c;账本上记录了公司成立以来每天的营业额。分析营业情况是一…csp信奥赛C标准模板库STL案例应用7set实践题目描述Tiger 最近被公司升任为营业部经理他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger 拿出了公司的账本账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日大减价或者是其他情况的时候营业额会出现一定的波动当然一定的波动是能够接受的但是在某些时候营业额突变得很高或是很低这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况当最小波动值越大时就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。我们定义一天的最小波动值 min ⁡ { ∣ 该天以前某一天的营业额 − 该天营业额 ∣ } \min\{|\text{该天以前某一天的营业额}-\text{该天营业额}|\}min{∣该天以前某一天的营业额−该天营业额∣}。特别地第一天的最小波动值为第一天的营业额。输入格式第一行为正整数n nnn ≤ 32767 n \leq 32767n≤32767 表示该公司从成立一直到现在的天数接下来的n nn行每行有一个整数a i a_iai​∣ a i ∣ ≤ 1 0 6 |a_i| \leq 10^6∣ai​∣≤106) 表示第i ii天公司的营业额可能存在负数。输出格式输出一个整数即每一天最小波动值的和保证结果小于2 31 2^{31}231。输入输出样例 1输入 16 5 1 2 5 4 6输出 112说明/提示结果说明5 ∣ 1 − 5 ∣ ∣ 2 − 1 ∣ ∣ 5 − 5 ∣ ∣ 4 − 5 ∣ ∣ 6 − 5 ∣ 5 4 1 0 1 1 12 5|1-5||2-1||5-5||4-5||6-5|541011125∣1−5∣∣2−1∣∣5−5∣∣4−5∣∣6−5∣54101112思路分析本题要求计算每天营业额的最小波动值之和。对于第 i 天的营业额需要在之前的所有营业额中找到与它最接近的值前驱或后继计算差的绝对值。核心思想使用平衡二叉搜索树这里用 C 的set来维护之前的所有营业额对于每个新的营业额用lower_bound找到第一个大于等于当前值的位置这个位置和它前一个位置如果存在就是与当前值最接近的两个候选值取这两个值与当前值差的最小值作为当天的最小波动值第一天特殊处理最小波动值就是当天的营业额时间复杂度使用set每次插入和查询都是 O(log n)总时间复杂度O(n log n)n ≤ 32767可以接受代码实现#includebits/stdc.husingnamespacestd;intn,sum0;// n: 天数sum: 最小波动值总和setints;// 用set存储之前的营业额自动排序intmain(){cinn;for(inti1;in;i){intx;cinx;// 读取当天的营业额// 如果是第一天特殊处理if(s.empty()){sumx;// 第一天最小波动值就是营业额本身s.insert(x);// 加入集合continue;}// 使用lower_bound找到第一个大于等于x的位置autoits.lower_bound(x);intansINT_MAX;// 初始化最小差值为最大整数// 检查后继如果存在if(it!s.end()){ansmin(ans,abs(*it-x));}// 检查前驱如果存在if(it!s.begin()){it--;// 移动到前一个位置ansmin(ans,abs(*it-x));}// 累加当天的最小波动值sumans;// 将当天营业额加入集合供后续使用s.insert(x);}coutsum;return0;}功能分析1. 数据结构选择使用setint自动排序可以快速查找前驱和后继基于红黑树实现插入和查找都是 O(log n) 时间复杂度2. 算法流程初始化读取天数 n初始化总和 sum 和集合 s处理每一天读取当天营业额 x如果集合为空第一天直接累加 x否则查找 x 在集合中的插入位置查找第一个 ≥ x 的数后继查找第一个 x 的数前驱取两者与 x 差的最小值累加到总和将 x 插入集合输出结果输出总和 sum3. 关键点lower_bound(x)返回第一个 ≥ x 的迭代器如果lower_bound返回end()说明没有 ≥ x 的数前驱检查it ! s.begin()确保有前一个元素第一天特殊处理最小波动值 当天营业额4. 示例解析输入6 5 1 2 5 4 6处理过程第1天sum5集合{5}第2天x1前驱/后继5差值4sum9集合{1,5}第3天x2前驱1(差1)后继5(差3)取1sum10集合{1,2,5}第4天x5找到相等的5差0sum10集合{1,2,5}第5天x4前驱2(差2)后继5(差1)取1sum11集合{1,2,4,5}第6天x6前驱5(差1)无后继取1sum12集合{1,2,4,5,6}各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转2025 csp-j 复赛真题及答案解析最新更新2025 csp-x(山东) 复赛真题及答案解析最新更新2025 csp-x(河南) 复赛真题及答案解析最新更新2025 csp-x(辽宁) 复赛真题及答案解析最新更新2025 csp-x(江西) 复赛真题及答案解析最新更新2025 csp-x(广西) 复赛真题及答案解析最新更新2020 ~ 2024 csp 复赛真题题单及题解2019 ~ 2022 csp-j 初赛高频考点真题分类解析2021 ~ 2024 csp-s 初赛高频考点解析2023 ~ 2024 csp-x (山东)初赛真题及答案解析2024 csp-j 初赛真题及答案解析2025 csp-j 初赛真题及答案解析最新更新2025 csp-s 初赛真题及答案解析最新更新2025 csp-x (山东)初赛真题及答案解析(最新更新)2025 csp-x (江西)初赛真题及答案解析(最新更新)2025 csp-x (辽宁)初赛真题及答案解析(最新更新)CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转129 道刷题练习和详细题解涉及模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图4、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}