? ? ? ? 相信大家對貪心算法已經見怪不怪了，但是一旦我們的決策條件會隨著我們的步驟變化，我們該怎么辦呢？有沒有什么方法可以反悔呢？

? ? ? ? 今天就來講可以后悔的貪心算法，反悔貪心。

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 don't 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?(2<=𝑁<=3?105), the number of days.

Following this is a line with exactly?𝑁N?integers?𝑝1,𝑝2,...,𝑝𝑁(1<=𝑝𝑖<=106)?. 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++.h>using namespace std;typedef long long LL;
const int N = 1e6 + 10;int p[N]; 
priority_queue<int, vector<int>, greater<int> > 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賬號哦>_<!!!