[HNOI2002] 營業(yè)額統(tǒng)計

STL - set解題

題目描述

Tiger 最近被公司升任為營業(yè)部經(jīng)理，他上任后接受公司交給的第一項任務便是統(tǒng)計并分析公司成立以來的營業(yè)情況。

Tiger 拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業(yè)額。分析營業(yè)情況是一項相當復雜的工作。由于節(jié)假日，大減價或者是其他情況的時候，營業(yè)額會出現(xiàn)一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業(yè)額突變得很高或是很低，這就證明公司此時的經(jīng)營狀況出現(xiàn)了問題。經(jīng)濟管理學上定義了一種最小波動值來衡量這種情況：當最小波動值越大時，就說明營業(yè)情況越不穩(wěn)定。

而分析整個公司的從成立到現(xiàn)在營業(yè)情況是否穩(wěn)定，只需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程序幫助 Tiger 來計算這一個值。

我們定義，一天的最小波動值 = min ? { ∣ 該天以前某一天的營業(yè)額 ? 該天營業(yè)額 ∣ } \min\{|\text{該天以前某一天的營業(yè)額}-\text{該天營業(yè)額}|\} min{∣該天以前某一天的營業(yè)額?該天營業(yè)額∣}。

特別地，第一天的最小波動值為第一天的營業(yè)額。

樣例輸入 #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$

題解

題意

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

數(shù)據(jù)約束

數(shù)據(jù)在Int范圍內

思路

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

參考代碼

#include <bits/stdc++.h>
using namespace std;
multiset<int> s;//數(shù)據(jù)存放在一個集合中 
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

特點：

• 無重復元素：不允許存儲重復的元素。
• 有序存儲：元素按某種規(guī)則（通常是升序）自動排序。
• 查找高效：可以高效查找某個元素是否存在。

例子：
想象你在一副撲克牌中找一張牌，牌面上沒有重復的牌。如果你想找某張牌，只需按順序查找，而不需要檢查重復。每張牌都按照花色和點數(shù)排序，保證沒有重復并且順序明確。。

set 是關聯(lián)容器的一種,是排序好的集合(自動排序) ，不能有重復的元素。

• 不能直接修改set容器中元素的值。因為元素被修改后,容器并不會自動重新調整順序，于是容器的有序性就會被破 壞，再在其上進行查找等操作就會得到錯誤的結果。若要修改set 容器中某個元素的值，則先刪除該元素，再插入新元素。
• multiset容器類似set容器 ，但它能保存重復的元素。(mult開頭有多個的意思 mutimedia多媒體，muticultural多元文化)
• set支持雙向迭代器，在插入和刪除時,所以不能直接采用迭代器++/–的方式。 v在STL中使用結構體 ，需要對特定要求的運算符進行重載;
• STL默認使用小于號來排序，因此，默認重載小于號: (如 果使用greater比較器就需重載大于號)，且要注意讓比較函數(shù)對相同元素返回false.

函數(shù)名	set 用法	map 用法	說明
insert	插入元素，返回迭代器mySet.insert(value)，	插入**鍵值對 ** myMap.insert({key, value}) 或myMap.insert(make_pair(key, value));	如果鍵已存在，則不會插入新鍵值對，直接返回已存在的迭代器
size	返回容器中元素的個數(shù)	同set
find	查找元素，返回迭代器mySet.find(value)	同set myMap.find(key)	若未找到則返回 end()迭代器
operator[]	-（不適用）	訪問/修改指定鍵對應的值（若鍵不存在則插入默認構造的值）
count	返回等于給定值的元素個數(shù) mySet.count(value);	返回鍵等于給定關鍵字的鍵值對個數(shù) myMap.count(key)	只能是 0 或 1）

通用的成員函數(shù)：

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; 	// 獲取元素個數(shù)mySet.erase(5); // 使用值刪除mySet.clear();// 清空容器cout<<"Size2: "<<mySet.size() <<endl;	// 獲取元素個數(shù)
------------------------------set<string> partyGuests; // 定義一個 set，模擬聚會的賓客名單partyGuests.insert("Alice");    // 添加一些賓客partyGuests.insert("Bob");partyGuests.insert("Charlie");partyGuests.insert("Alice");  // Alice 已經(jīng)在名單上了，不會重復添加// 輸出所有的賓客，按照字母順序排列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;    // 查看聚會的賓客人數(shù)if (partyGuests.empty()) {    // 查看聚會是否為空cout << "聚會沒有賓客。" << endl;}partyGuests.clear();  // 聚會取消，清空所有賓客cout << "聚會已取消，清空所有賓客。" << endl;

自定義排序規(guī)則

• set 會使用元素類型的 < 運算符對元素進行升序排序。
• 可以通過指定自定義的比較器來改變排序規(guī)則，例如使用 greater<T> 來實現(xiàn)降序排序，或者自定義一個比較器來按特定的規(guī)則排序。
• 自定義排序規(guī)則通常是通過提供一個**函數(shù)對象（結構體或函數(shù)指針）**實現(xiàn)的。
• 對于基本類型（如 int、double 等），默認按照升序排列。對于自定義類型（如類或結構體），set 默認使用 < 運算符進行排序。如果你沒有為自定義類型定義 < 運算符，編譯器會報錯。

（按字符串長度排序）

假設你有一個 set 來存儲字符串，并希望按字符串的長度進行排序（而不是字母順序）。你可以通過自定義比較器來實現(xiàn)：

#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 表達式定義降序排序規(guī)則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;
}