建公司网站设计网站公司,优品ppt模板免费下载网站,wordpress 微信咨询菜单,wordpress 主题版权相信大家对贪心算法已经见怪不怪了#xff0c;但是一旦我们的决策条件会随着我们的步骤变化#xff0c;我们该怎么办呢#xff1f;有没有什么方法可以反悔呢#xff1f; 今天就来讲可以后悔的贪心算法#xff0c;反悔贪心。
https://www.luogu.com.cn/problem/CF865Dhttp… 相信大家对贪心算法已经见怪不怪了但是一旦我们的决策条件会随着我们的步骤变化我们该怎么办呢有没有什么方法可以反悔呢 今天就来讲可以后悔的贪心算法反悔贪心。
https://www.luogu.com.cn/problem/CF865Dhttps://www.luogu.com.cn/problem/CF865D
题目描述 You can perfectly predict the price of a certain stock for the next days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you dont own any. At the end of the days you would like to again own zero shares, but want to have as much money as possible.
输入格式
Input begins with an integer N (23⋅105), the number of days.
Following this is a line with exactly N integers 1,2,...,(1106) . The price of one share of stock on the -th day is given by .
输出格式
Print the maximum amount of money you can end up with at the end of days.
输入输出样例
输入 #1
9
10 5 4 7 9 12 6 2 10输出 #1
20输入 #2
20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4输出 #2
41 就像买卖股票谁都不知道接下来股票的趋势但如果我们知道了趋势又如何让自己的收益最大化呢 因此我们可以先考虑两种情况 一当第一天的价格高于第二天时我们就只要屯着因为卖出去是没有收益的。 二反之我们每次遇见第二天的价格高于第一天时我们就直接先考虑卖出(能赚一点是一点)我们会获得收益那假如之后价格更高怎么办当然是反悔了我们用一个小根堆来存储已经路过的天数,秉承着只要有钱赚就卖的原则我们充分利用priority_queue的强大优势当堆顶元素比当日价格低的时候我们就卖掉映射到代码就是pop()然后将总获利加上差价就是买股票的钱那么怎么反悔呢我们在pop堆顶元素的时候将一个当日的股价压入堆无论在哪里只要堆不空那么只要有股价高于堆顶元素的就重复以上步骤这样做不会舍弃更高的利润而是将难以维护的决策变成了类似滚雪球一样的方式这就是反悔贪心的核心操作。比较抽象需要仔细理解体会。 最后附上完整代码
#include bits/stdc.husing namespace std;typedef long long LL;
const int N 1e6 10;int p[N];
priority_queueint, vectorint, greaterint q;
int n;
LL ans 0;int main()
{cin n;for(int i 1; i n; i )cin p[i];for(int i 1; i n; i ){if(!q.empty() p[i] q.top()){ans p[i] - q.top();q.pop();q.push(p[i]);}q.push(p[i]);}cout ans endl;
} tip这是一次CF上的题在洛谷上提交的时候要记得绑定CF账号哦_!!!
