【題目來源】
https://www.luogu.com.cn/problem/P2234

【題目描述】
Tiger 最近被公司升任為營業部經理，他上任后接受公司交給的第一項任務便是統計并分析公司成立以來的營業情況。
Tiger 拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當復雜的工作。由于節假日，大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況：當最小波動值越大時，就說明營業情況越不穩定。
而分析整個公司的從成立到現在營業情況是否穩定，只需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程序幫助 Tiger 來計算這一個值。
我們定義，一天的最小波動值 = min{∣該天以前某一天的營業額?該天營業額∣}。
特別地，第一天的最小波動值為第一天的營業額。

【輸入格式】
第一行為正整數 n（n≤32767） ，表示該公司從成立一直到現在的天數，接下來的 n 行每行有一個整數 ai（∣ai∣≤10^6) ，表示第 i 天公司的營業額，可能存在負數。

【輸出格式】
輸出一個正整數，即每一天最小波動值的和，保證結果小于 2^31。

【輸入樣例】
6
5
1
2
5
4
6

【輸出樣例】
12

【說明/提示】
結果說明：5+∣1?5∣+∣2?1∣+∣5?5∣+∣4?5∣+∣6?5∣=5+4+1+0+1+1=12

【算法分析】
● STL set 常用函數解析
https://blog.csdn.net/hnjzsyjyj/article/details/127017796
https://blog.csdn.net/hnjzsyjyj/article/details/145528031

● 代碼邏輯解析
?（一）初始化階段?
在集合 s 中預先插入 inf 和 -inf，確保后續查找操作始終存在前驅和后繼節點，避免空集合導致的異常?。注意：此處的無窮大 inf 設為 0x3f3f3f3f，不要設為 0x7f7f7f7f。這是因為，0x7f7f7f7f 的缺點是容易在加法運算中溢出，導致負數結果，這在算法中可能引發錯誤?。
?（二）輸入處理階段?
讀取整數 n，循環處理每個輸入值 x。
?1.當集合僅含初始邊界?inf 和 -inf?時?（s.size() == 2），直接插入 x 并將 x 累加到答案 ans 中。
?2. 當集合已有其他元素時?：
（1）使用 lower_bound(x) 找到第一個大于等于 x 的迭代器 it?。
（2）若 *it != x（即 x 不存在于集合中），計算 x 與 *it（后繼）和 *--t（前驅）的最小差值，累加到 ans。
（3）插入 x 到集合中。
（三）輸出結果?
最終輸出累加的最小差值總和 ans。

● 計算過程詳析
1.輸入 5 時 → 集合初始只有兩個邊界 → ans+=5 → 插入 5
2.輸入 1 時 → 前驅 -inf，后繼 5 → 最小差值 4 → ans+=4 → 插入 1
3.輸入 2 時 → 前驅 1，后繼 5 → 最小差值1 → ans+=1 → 插入 2
4.輸入 5 時 → 已存在，不處理
5.輸入 4 時 → 前驅 2，后繼 5 → 最小差值 1 → ans+=1 → 插入 4
6.輸入 6 時 → 前驅 5，后繼 inf → 最小差值 1 → ans+=1 → 插入 6
累計總和：5+4+1+1+1=12

● ???????適用場景
該算法適用于需要動態維護有序序列，并在每次插入時快速計算與相鄰元素的最小差值的場景，如實時數據流分析或特定競賽題目?。

【算法代碼】

#include <bits/stdc++.h>
using namespace std;const int inf=0x3f3f3f3f;
set<int> s;
set<int>::iterator it,t;
int x,ans;
int n;int main() {s.insert(inf);s.insert(-inf);cin>>n;while(n--) {cin>>x;if(s.size()==2) {s.insert(x);ans+=x;} else {it=s.lower_bound(x);if(*it!=x) {t=it, t--;ans+=min(abs(x-*it),abs(x-*t));s.insert(x);}}}cout<<ans<<endl;return 0;
}/*
in:
6
5
1
2
5
4
6out:
12
*/

【參考文獻】
https://blog.csdn.net/hnjzsyjyj/article/details/145528031
https://blog.csdn.net/hnjzsyjyj/article/details/146110033


?