自己想了好一会,AC后看了下好像和网上挺多人思路不太一样(但本质是一样的),所以就来写这篇题解
首先这题之所以能反悔的根本原因和性质在于你在第i天买股票,第j天卖出,可以拆成第i天买股票,第k(i <= k <= j)天卖出和第k天买股票,第j天卖出两个过程(I)
我们首先可以从大到小倒序扫描,假设当前扫到某个数i,然后贪心地想如果后面的最大值可以大于当前这个值,那就买入这个数,在最大值的位置卖出,这时我们要分两种情况考虑,
(1)
如果后面那个数(即最大值,记为k)已经买入过了,那么意味它后面肯定还有一个比它更大的值j,于是我们可以根据性质I,把i塞入堆里,标记为已经买过,而把k更新为标记没有买入过,重新塞入堆里.
(2)
如果这个数k没有被买入过,那么我们应该直接把它弹出(因为它不能像性质I那样作为中转点,所以只能卖出),同时把i标记为已经买入过,塞入堆里
代码如下
/*CF865D Buy Low Sell High*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
struct Num{
int v,op;
};
bool operator < (Num A,Num B) {
return A.v < B.v;
}
priority_queue<Num>q;
int read(){
char c = getchar();
int x = 0;
while(c < ‘0‘ || c > ‘9‘) c = getchar();
while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48,c = getchar();
return x;
}
ll ans = 0;
const int maxn = 1e6 + 10;
int p[maxn];
int main()
{
int n = read();
for(int i = 1; i <= n; ++i)
p[i] = read();
for(int i = n; i >= 1; --i){
if(i == n){
q.push(Num{p[i],1});
continue;
}
Num x = q.top();
if(x.v <= p[i]){
q.push(Num{p[i],1});
}
else{
if(x.op == -1){
int v = x.v;
q.pop();
q.push(Num{v,1});
ans += v - p[i];
q.push(Num{p[i],-1});
}
else{
int v = x.v;
ans += v - p[i];
q.pop();
q.push(Num{p[i],-1});
}
}
}
cout<<ans<<endl;
return 0;
}
CF865D Buy Low Sell High(反悔贪心)
原文：https://www.cnblogs.com/y-dove/p/13562592.html