英语工作室网站怎么做,商务网站建设ppt,网站地址英文,免费seo网站自动推广软件1. 相近的营业额
1.1 题目
题目描述#xff1a;我们定义#xff0c;一天营业额的最小波动 min { | 该天以前某一天的营业额 - 该天营业额 | } 特别的#xff0c;第一天的营业额最小波动为第一天的营业额
输入描述#xff1a;第一行 n #xff08;n 32767#xf…1. 相近的营业额
1.1 题目
题目描述我们定义一天营业额的最小波动 min { | 该天以前某一天的营业额 - 该天营业额 | } 特别的第一天的营业额最小波动为第一天的营业额
输入描述第一行 n n 32767表示公司从成立到现在的天数 接下来 n 行每行有一个整数 ai |ai| 10e6表示第 i 天的营业额可能存在负数
输出描述一个正整数表示每一天最小波动的和保证结果小于 2^31
输入
6
5
1
2
5
4
6
输出
12
1.2 思想
对于每一个新的数 x 我们总共要找到距离 x 最近的一大一小的两个数可以将之前的数据放入到 set 中对于大于等于 x 的值可以用 lower_bound 得到 set 中该值的迭代器让迭代器进行--操作可以得到比 x 小的最接近 x 的值然后让各自与 x 的差值进行比较就可以得到最小波动值
值得注意的是当对迭代器进行--操作时如果 set 里的元素不够可能非法访问所以我们需要左右护法进行保护而左右护法也不能干涉比较的结果那左右护法可以趋于无穷即这个情况下不可能取到的值
1.3 模拟实现
#includeiostream
using namespace std;
#includeset
#includecmath
setint mp;
//注意近似无穷的值
int INF 1e710;
int total;
int main()
{int n; cin n;int x; cin x;//先将第一天的值插入mp.insert(x);total x;//添加左右护法mp.insert(INF);mp.insert(-INF);for(int i2;in;i){int x; cin x;//取出大于等于 x 的值的迭代器auto it1 mp.lower_bound(x);//找到最近的小于 x 的迭代器auto it2 it1;it2--;//进行比较total min(abs( *it1 - x ), abs( *it2 - x ));//最后将今天的 x 插入mp.insert(x);}cout total endl;return 0;
}
2. 相近的木材
2.1 题目
题目描述有一个木材仓库里面没有两个木材的长度相同现在有不超过100000条操作 进货格式1 length向仓库中放入长度为 length 不超过 10e9的木材如果已经存在就输出 Already Exist 出货格式2 length仓库中取出长度为 length 的木材。如果没有刚好长度的木材取 出仓库中存在的和要求长度最接近的木材。如果有多个符合要求取出比较短。输出取出的木材长度。如果仓库为空输出 Empty
输入
7 1 1 1 5 1 3 2 3 2 3 2 3 2 3
输出
3 1 5 Empty 2.2 思想
和上面的解法类似对于要删除的数 x 我们总共要找到距离 x 最近的一大一小的两个数可以将之前的数据放入到 set 中对于大于等于 x 的值可以用 lower_bound 得到 set 中该值的迭代器让迭代器进行--操作可以得到比 x 小的最接近 x 的值然后让各自与 x 的差值进行比较就可以得到要删除的值
值得注意的是当对迭代器进行--操作时如果 set 里的元素不够可能非法访问所以我们需要左右护法进行保护而左右护法也不能干涉比较的结果那左右护法可以趋于无穷即这个情况下不可能取到的值
2.3 模拟实现
#includeiostream
using namespace std;
#includeset
#includecmath
typedef long long LL;
//注意元素的范围
setLL mp;
//左右护法该情况下可以看作趋于无穷
LL INF 1e10 10;int main()
{int n; cin n;while (n--){LL op, x; cin op x;//添加左右护法mp.insert(INF); mp.insert(-INF);if (op 1){//如果 set 没有就插入if (mp.count(x)) cout Already Exist endl;else mp.insert(x);}else{//只有左右护法可以将 set 看作空if (mp.size() 2) cout Empty endl;else{//取出大于等于 x 的值的迭代器auto it1 mp.lower_bound(x);//找到最近的小于 x 的迭代器auto it2 it1;it2--;//进行比较if (abs(*it1 - x) abs(*it2 - x)){cout *it2 endl;mp.erase(*it2);}else{cout *it1 endl;mp.erase(*it1);}}}}return 0;
}
