CodeVS 1296 营业额统计
2024-08-31 15:22:59
1296 营业额统计2002年
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：
该天的最小波动值 = min{|该天以前某一天的营业额-该天营业额|}
当最小波动值越大时，就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
第一天的最小波动值为第一天的营业额。
输入描述 Input Description
第一行为正整数n(n<=32767)，表示该公司从成立一直到现在的天数，接下来的n行每行有一个正整数ai(ai<=1000000)，表示第i天公司的营业额。
输出描述 Output Description
输出文件仅有一个正整数，即每天最小波动值之和，小于231
样例输入 Sample Input
6
5
1
2
5
4
6
样例输出 Sample Output
12
数据范围及提示 Data Size & Hint
结果说明：$5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12$
解题：利用平衡树的前后驱节点的查询。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
multiset<int>s;
int main() {
int n,tmp;
LL ret = ;
scanf("%d",&n);
for(int i = ; i < n; ++i) {
scanf("%d",&tmp);
if(i) {
multiset<int>::iterator it = s.lower_bound(tmp);
if(it == s.end()) {
it--;
ret += abs(*it - tmp);
} else {
int ntmp = abs(*it - tmp);
if(it!=s.begin()) {
it--;
ntmp = min(ntmp,abs((*it) - tmp));
}
ret += ntmp;
}
s.insert(tmp);
} else {
ret = tmp;
s.insert(tmp);
}
}
cout<<ret<<endl;
return ;
}
最新文章
- zeromq中两个dealer 通过一个router进行通信
- apache 自带的ab测试
- JMeter学习-024-JMeter 命令行（非GUI）模式详解（二）-执行代理设置
- PRML读书会第十章 Approximate Inference（近似推断，变分推断，KL散度，平均场， Mean Field ）
- 流媒体选择Nginx是福还是祸？
- 原生DOM探究 -- NodeList v.s. HTMLCollection
- 51nod贪心算法入门-----活动安排问题2
- Win异常： 除了chrome浏览器外，所有安装的软件都连不上网
- 微信开放平台获取component_verify_ticket
- Qt入门（12）——Qt国际化
- SQL：deferrable initially deferred
- android离线缓存技术
- Element老司机开车了
- day31并发
- HTTP常用头部信息
- Java替换中使用正则表达式实现中间模糊匹配
- React-理解Redux
- 九：python 对象类型详解五：元组
- 45度炸队Alpha冲刺博客集
- cinder侧卸载卷流程分析