40 lines
1.3 KiB
C++
40 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
set<int> s;//set 自带排序功能，强！set本身就是一种有序的容器。
|
||
int n, x, ans;
|
||
//需要单独训练一下 stl set这种数据结构
|
||
int main() {
|
||
//set中放入极大和极小值,这个放入极大与极小值的技巧太棒了，可以有效避免越界等问题，值得背诵~
|
||
s.insert(INF);
|
||
s.insert(-INF);
|
||
//读入
|
||
cin >> n;
|
||
for (int i = 1; i <= n; ++i) {
|
||
cin >> x;
|
||
//如果set是空，只有极大与极小值时.也就是第一个
|
||
if (s.size() == 2) {
|
||
ans += x;
|
||
s.insert(x);
|
||
} else {
|
||
//set居然支持二分法搜索~太棒了
|
||
//lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素
|
||
auto k = s.lower_bound(x);
|
||
//如果不相等时（相等就是零了，不需要加入）
|
||
if (*k != x) {
|
||
//复制出来迭代器
|
||
auto a = k;
|
||
//前驱
|
||
a--;
|
||
//最小波动值和
|
||
ans += min(abs(*a - x), abs(*k - x));
|
||
//金额入集合
|
||
s.insert(x);
|
||
}
|
||
}
|
||
}
|
||
//输出结果
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |