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

STL - set解題

題目描述

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

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

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

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

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

樣例輸入 #1

6
5
1
2
5
4
6

樣例輸出 #1

12

提示

結(jié)果說明：$5+|1?5|+|2?1|+|5?5|+|4?5|+|6?5|=5+4+1+0+1+1=12$

題解

題意

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

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

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

思路

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

參考代碼

#include <bits/stdc++.h>
using namespace std;
multiset<int> s;//數(shù)據(jù)存放在一個(gè)集合中 
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()){ //不是最后一個(gè)if(ad!=s.end()){ //不是最后一個(gè)maxx  = abs(*ad - k);ad--;}else{ad--;}//處理前一個(gè)if(ad!=s.begin()){ad--;minn  = abs(*ad - k) ;}ans += min(maxx,minn);}}cout<<ans;}

相關(guān)知識(shí)點(diǎn)

set

特點(diǎn)：

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

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

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

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

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

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

end 返回指向容器中最后一個(gè)元素之后位置的迭代器 返回指向容器中最后一個(gè)鍵值對(duì)之后位置的迭代器

begin 返回指向容器中第一個(gè)元素的迭代器 同set

clear 清空容器，刪除所有元素 清空容器，刪除所有鍵值對(duì)

erase 刪除元素，可通過迭代器或值刪除 刪除鍵值對(duì)，可通過迭代器或鍵刪除 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; 	// 獲取元素個(gè)數(shù)mySet.erase(5); // 使用值刪除mySet.clear();// 清空容器cout<<"Size2: "<<mySet.size() <<endl;	// 獲取元素個(gè)數(shù)
------------------------------set<string> partyGuests; // 定義一個(gè) set，模擬聚會(huì)的賓客名單partyGuests.insert("Alice");    // 添加一些賓客partyGuests.insert("Bob");partyGuests.insert("Charlie");partyGuests.insert("Alice");  // Alice 已經(jīng)在名單上了，不會(huì)重復(fù)添加// 輸出所有的賓客，按照字母順序排列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"); // 查找某個(gè)賓客if (search_it != partyGuests.end()) {cout << "Charlie 已被邀請(qǐng)參加聚會(huì)！" << endl;} else {cout << "Charlie 沒有被邀請(qǐng)。" << endl;}partyGuests.erase("Bob");  //  // 刪除某個(gè)賓客 Bob 不來了，移除他cout << "當(dāng)前聚會(huì)有 " << partyGuests.size() << " 位賓客。" << endl;    // 查看聚會(huì)的賓客人數(shù)if (partyGuests.empty()) {    // 查看聚會(huì)是否為空cout << "聚會(huì)沒有賓客。" << endl;}partyGuests.clear();  // 聚會(huì)取消，清空所有賓客cout << "聚會(huì)已取消，清空所有賓客。" << endl;

自定義排序規(guī)則

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

（按字符串長(zhǎng)度排序）

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

#include <iostream>
#include <set>
#include <string>
using namespace std;
// 自定義比較器，按字符串長(zhǎng)度排序
struct CompareByLength {bool operator()(const string& a, const string& b) const {return a.length() < b.length();  // 按長(zhǎng)度升序排列}
};
int main() {// 使用 lambda 表達(dá)式定義降序排序規(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");// 輸出按字符串長(zhǎng)度排序的元素for (const string& str : s) {cout << str << " ";  // 輸出 kiwi apple orange banana}return 0;
}