[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$

題解

題意

統計最小的差值和，要每天的波動的差值最小，即 min = 最相近的一個數-當前值 例如 1 2 3 5 8 中 第三天的最小值min = abs(2-3) = 1

數據約束

數據在Int范圍內

思路

1. 由分析看得出，需要排序所有的數，然后取相近的-左右兩邊的數分別求差值 再求最小值
2. 如果按照常規的數據處理，數組排序，然后在前后遍歷顯然很麻煩，只是處理找數據，所以考慮容器。set map都能自動排序，顯然選set
3. 從樣例可以看得出來，數據不能做去重處理，所以直接使用mutiset即可

參考代碼

#include <bits/stdc++.h>
using namespace std;
multiset<int> s;//數據存放在一個集合中 
int main() {int n,ans=0;int minn=1e10,maxx=1e10,k;cin>>n;for(int i=0;i<n;i++){minn=1e10,maxx=1e10;//每次都初始化一下 cin>>k;s.insert(k);
//		multiset<int> ::iterator it;
//		for(it=s.begin();it!=s.end();it++){
//			cout<<*it<<" ";
//		}
//		cout<<endl;if(i==0){ans += k;}else{multiset<int> ::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);}}cout<<ans;}

相關知識點

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	返回容器中元素的個數	同set
find	查找元素，返回迭代器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);

	set<int> mySet;mySet.insert(5);// 插入元素mySet.insert(2);mySet.insert(8);mySet.insert(1);// 查找元素（返回迭代器）set<int>::iterator it=mySet.find(1);if (it!=mySet.end()) {cout<<"Found: "<<*it<<endl;}mySet.erase(it);// 刪除元素cout<<"Size1: "<<mySet.size() <<endl; 	// 獲取元素個數mySet.erase(5); // 使用值刪除mySet.clear();// 清空容器cout<<"Size2: "<<mySet.size() <<endl;	// 獲取元素個數
------------------------------set<string> partyGuests; // 定義一個 set，模擬聚會的賓客名單partyGuests.insert("Alice");    // 添加一些賓客partyGuests.insert("Bob");partyGuests.insert("Charlie");partyGuests.insert("Alice");  // Alice 已經在名單上了，不會重復添加// 輸出所有的賓客，按照字母順序排列for (set<string>::iterator it = partyGuests.begin(); it != partyGuests.end(); it++) {cout << *it << " ";}cout << endl;  // 輸出：Alice Bob Charlieset<string>::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 會使用元素類型的 < 運算符對元素進行升序排序。
• 可以通過指定自定義的比較器來改變排序規則，例如使用 greater<T> 來實現降序排序，或者自定義一個比較器來按特定的規則排序。
• 自定義排序規則通常是通過提供一個**函數對象（結構體或函數指針）**實現的。
• 對于基本類型（如 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 表達式定義降序排序規則set<int, greater<int>> s;  s.insert(5);s.insert(2);s.insert(8);// 輸出按降序排列的元素for (int num : s) {cout << num << " ";  // 輸出 8 5 2 }set<string, 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;
}