作者：6057318491 | 来源：互联网 | 2024-10-09 08:34
这道贪心非常神仙大体想法肯定是选择一个价格较低的一天买入并在之后找一个价格较高的一天卖出直接贪心的选显然不可行，考虑如何实现“反悔”这里直接说做法，反正我也想不到从前向后扫描每一天
这道贪心非常神仙
大体想法肯定是选择一个价格较低的一天买入
并在之后找一个价格较高的一天卖出
直接贪心的选显然不可行，考虑如何实现“反悔”
这里直接说做法，反正我也想不到= =
从前向后扫描每一天，若当前价格比堆顶还小就入堆
否则，将从堆顶买入并从当天卖出，弹出堆顶，并将当天价格入堆两次
这里解释一下入堆两次的道理
如果之后有一天价格更高，可以借助其中入堆的一个值反悔，
相当于从那次的堆顶买入，价格更高的这天卖出
而如果有这次反悔，相当于那天并没有进行操作
这时候多入堆的那次就有用了
这样以后它作为堆顶之后，就相当于在那天买入后边卖出了
代码：
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN = 300005;
int n;
int p[MAXN];
ll ans;
priority_queue q;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &p[i]);
for(int i = 1; i <= n; ++i) {
if(q.empty() || -q.top() > p[i]) q.push(-p[i]);
else {
ans += q.top();
q.pop();
ans += p[i];
q.push(-p[i]);
q.push(-p[i]);
}
}
printf("%lld\n", ans);
return 0;
}
京公网安备 11010802041100号