59 lines
1.9 KiB
C++
59 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 32768;
|
||
int ans;
|
||
|
||
//结构体：某一天
|
||
//money:营业额，day:第day天
|
||
struct node {
|
||
int money;
|
||
int day;
|
||
} s[N];
|
||
|
||
//结构体的比较函数，以钱小在前，钱大在后进行排序
|
||
bool cmp(node x, node y) {
|
||
return x.money < y.money;
|
||
}
|
||
|
||
//双链表的声明
|
||
int n, nex[N], pre[N], a[N];
|
||
|
||
int main() {
|
||
//输入
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
cin >> a[i]; //原始数组,第1，2，3 ...天的营业额是多少
|
||
s[i] = {a[i], i}; //为了按营业额排序，但还需要保留是哪天的信息，没办法，只能使用结构体
|
||
}
|
||
//排序
|
||
sort(s + 1, s + 1 + n, cmp);//按金额由小到大排序
|
||
|
||
//"动态查找前驱后继"，可以用链表的离线做法
|
||
//创建结构体+双链表,按金额排序后，日期的前后关系。
|
||
for (int i = 1; i <= n; i++) {
|
||
nex[s[i].day] = s[i + 1].day;
|
||
pre[s[i].day] = s[i - 1].day;
|
||
}
|
||
|
||
//从后向前,这个非常棒！这样的话，就可以无视前驱和后继的概念，不管是存在前驱还是后继，其实都是前面的日子金额，全可以用。
|
||
//用后最删除，不影响其它日期判断
|
||
for (int i = n; i >= 1; i--) {
|
||
//没有后继,有前驱
|
||
if (nex[i] == 0 && pre[i] > 0)ans += abs(a[i] - a[pre[i]]);
|
||
//没有前驱,有后继
|
||
else if (nex[i] > 0 && pre[i] == 0) ans += abs(a[i] - a[nex[i]]);
|
||
//有前驱有后继
|
||
else if (pre[i] > 0 && nex[i] > 0)ans += min(abs(a[nex[i]] - a[i]), abs(a[pre[i]] - a[i]));
|
||
//无前驱，无后继
|
||
else if (pre[i] == 0 && nex[i] == 0)ans += a[i];
|
||
//删除当前结点,防止前面的节点错误的找到它
|
||
nex[pre[i]] = nex[i];
|
||
pre[nex[i]] = pre[i];
|
||
}
|
||
|
||
//输出
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |