洛谷 CF865D. Buy Low Sell High
原题链接
简单
作者:
y总的小迷弟
,
2023-10-01 17:01:50
,
所有人可见
,
阅读 61
//反悔贪心:反悔堆;
//错误的策略:每次碰到大的就直接贪,但这显然不对,因为以后可能会遇到更大的;
//设三天价格分别为pi,pj,pk(pi<pj<pk);我们先用pj-pi累加答案,再把pj放入堆中,然后pk-pj又会更新答案,我们惊奇的发现,pj被抵消了,pk-pi就是我们想要的;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, ans = 0;
ll p[300010];
priority_queue<ll, vector<ll>, greater<ll>> heap;
int main()
{
cin >> n;
for(int i = 1;i <= n;i++)
cin >> p[i];
for(int i = 1;i <= n;i++)
{
if(!heap.empty() && p[i] > heap.top())
{
ans += p[i] - heap.top();
heap.pop();//这里是为了“pk-pj又会更新答案”
heap.push(p[i]);
}
heap.push(p[i]);//这里是为了“pj-pi累加答案”
}
cout <<ans <<endl;
return 0;
}