龙华网站建设设计公司,网站规划与设计范文,怎么做网页的超链接,湘潭营销网站建设文章目录 [HNOI2002] 营业额统计题目描述样例输入 #1样例输出 #1 提示题解相关知识点set [HNOI2002] 营业额统计
STL - set解题
题目描述
Tiger 最近被公司升任为营业部经理#xff0c;他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger 拿出… 文章目录 [HNOI2002] 营业额统计题目描述样例输入 #1样例输出 #1 提示题解相关知识点set [HNOI2002] 营业额统计
STL - set解题
题目描述
Tiger 最近被公司升任为营业部经理他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger 拿出了公司的账本账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日大减价或者是其他情况的时候营业额会出现一定的波动当然一定的波动是能够接受的但是在某些时候营业额突变得很高或是很低这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况当最小波动值越大时就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。
我们定义一天的最小波动值 min { ∣ 该天以前某一天的营业额 − 该天营业额 ∣ } \min\{|\text{该天以前某一天的营业额}-\text{该天营业额}|\} min{∣该天以前某一天的营业额−该天营业额∣}。
特别地第一天的最小波动值为第一天的营业额。
样例输入 #1
6
5
1
2
5
4
6样例输出 #1
12提示
结果说明 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|54101112 5∣1−5∣∣2−1∣∣5−5∣∣4−5∣∣6−5∣54101112
题解
题意
统计最小的差值和要每天的波动的差值最小即 min 最相近的一个数-当前值 例如 1 2 3 5 8 中 第三天的最小值min abs(2-3) 1
数据约束
数据在Int范围内
思路
由分析看得出需要排序所有的数然后取相近的-左右两边的数分别求差值 再求最小值如果按照常规的数据处理数组排序然后在前后遍历显然很麻烦只是处理找数据所以考虑容器。set map都能自动排序显然选set从样例可以看得出来数据不能做去重处理所以直接使用mutiset即可
参考代码
#include bits/stdc.h
using namespace std;
multisetint s;//数据存放在一个集合中
int main() {int n,ans0;int minn1e10,maxx1e10,k;cinn;for(int i0;in;i){minn1e10,maxx1e10;//每次都初始化一下 cink;s.insert(k);
// multisetint ::iterator it;
// for(its.begin();it!s.end();it){
// cout*it ;
// }
// coutendl;if(i0){ans k;}else{multisetint ::iterator ad;ad s.find(k);ad;
// if((ad)!s.end()){ //不是最后一个if(ad!s.end()){ //不是最后一个maxx abs(*ad - k);ad--;}else{ad--;}//处理前一个if(ad!s.begin()){ad--;minn abs(*ad - k) ;}ans min(maxx,minn);}}coutans;}相关知识点
set
特点
无重复元素不允许存储重复的元素。有序存储元素按某种规则通常是升序自动排序。查找高效可以高效查找某个元素是否存在。
例子 想象你在一副扑克牌中找一张牌牌面上没有重复的牌。如果你想找某张牌只需按顺序查找而不需要检查重复。每张牌都按照花色和点数排序保证没有重复并且顺序明确。。
set 是关联容器的一种,是排序好的集合(自动排序) 不能有重复的元素。
不能直接修改set容器中元素的值。因为元素被修改后,容器并不会自动重新调整顺序于是容器的有序性就会被破 坏再在其上进行查找等操作就会得到错误的结果。若要修改set 容器中某个元素的值则先删除该元素再插入新元素。multiset容器类似set容器 但它能保存重复的元素。(mult开头有多个的意思 mutimedia多媒体muticultural多元文化)set支持双向迭代器在插入和删除时,所以不能直接采用迭代器/–的方式。 v在STL中使用结构体 需要对特定要求的运算符进行重载;STL默认使用小于号来排序因此默认重载小于号: (如 果使用greater比较器就需重载大于号)且要注意让比较函数对相同元素返回false.
函数名set 用法map 用法说明insert 插入元素返回迭代器mySet.insert(value)插入**键值对 ** myMap.insert({key, value}) 或myMap.insert(make_pair(key, value));如果键已存在则不会插入新键值对直接返回已存在的迭代器size返回容器中元素的个数同setfind查找元素返回迭代器mySet.find(value)同set myMap.find(key)若未找到则返回 end()迭代器operator[] -不适用访问/修改指定键对应的值若键不存在则插入默认构造的值count返回等于给定值的元素个数 mySet.count(value);返回键等于给定关键字的键值对个数 myMap.count(key)只能是 0 或 1
通用的成员函数
end 返回指向容器中最后一个元素之后位置的迭代器 返回指向容器中最后一个键值对之后位置的迭代器
begin 返回指向容器中第一个元素的迭代器 同set
clear 清空容器删除所有元素 清空容器删除所有键值对
erase 删除元素可通过迭代器或值删除 删除键值对可通过迭代器或键删除 mySet.erase(it);或mySet.erase(value); setint mySet;mySet.insert(5);// 插入元素mySet.insert(2);mySet.insert(8);mySet.insert(1);// 查找元素返回迭代器setint::iterator itmySet.find(1);if (it!mySet.end()) {coutFound: *itendl;}mySet.erase(it);// 删除元素coutSize1: mySet.size() endl; // 获取元素个数mySet.erase(5); // 使用值删除mySet.clear();// 清空容器coutSize2: mySet.size() endl; // 获取元素个数
------------------------------setstring partyGuests; // 定义一个 set模拟聚会的宾客名单partyGuests.insert(Alice); // 添加一些宾客partyGuests.insert(Bob);partyGuests.insert(Charlie);partyGuests.insert(Alice); // Alice 已经在名单上了不会重复添加// 输出所有的宾客按照字母顺序排列for (setstring::iterator it partyGuests.begin(); it ! partyGuests.end(); it) {cout *it ;}cout endl; // 输出Alice Bob Charliesetstring::iterator search_it partyGuests.find(Charlie); // 查找某个宾客if (search_it ! partyGuests.end()) {cout Charlie 已被邀请参加聚会 endl;} else {cout Charlie 没有被邀请。 endl;}partyGuests.erase(Bob); // // 删除某个宾客 Bob 不来了移除他cout 当前聚会有 partyGuests.size() 位宾客。 endl; // 查看聚会的宾客人数if (partyGuests.empty()) { // 查看聚会是否为空cout 聚会没有宾客。 endl;}partyGuests.clear(); // 聚会取消清空所有宾客cout 聚会已取消清空所有宾客。 endl;自定义排序规则
set 会使用元素类型的 运算符对元素进行升序排序。可以通过指定自定义的比较器来改变排序规则例如使用 greaterT 来实现降序排序或者自定义一个比较器来按特定的规则排序。自定义排序规则通常是通过提供一个**函数对象结构体或函数指针**实现的。对于基本类型如 int、double 等默认按照升序排列。对于自定义类型如类或结构体set 默认使用 运算符进行排序。如果你没有为自定义类型定义 运算符编译器会报错。
按字符串长度排序
假设你有一个 set 来存储字符串并希望按字符串的长度进行排序而不是字母顺序。你可以通过自定义比较器来实现
#include iostream
#include set
#include string
using namespace std;
// 自定义比较器按字符串长度排序
struct CompareByLength {bool operator()(const string a, const string b) const {return a.length() b.length(); // 按长度升序排列}
};
int main() {// 使用 lambda 表达式定义降序排序规则setint, greaterint s; s.insert(5);s.insert(2);s.insert(8);// 输出按降序排列的元素for (int num : s) {cout num ; // 输出 8 5 2 }setstring, CompareByLength s;s.insert(apple);s.insert(banana);s.insert(kiwi);s.insert(orange);// 输出按字符串长度排序的元素for (const string str : s) {cout str ; // 输出 kiwi apple orange banana}return 0;
}
