貪心算法拓展(反悔貪心)

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

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

https://www.luogu.com.cn/problem/CF865Dicon-default.png?t=N7T8https://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賬號哦>_<!!!

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/21543.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/21543.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/21543.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

C++棧、隊列

文章目錄 目錄 文章目錄 前言 一、stack、queue介紹 1.stack 2.queue 二、stack、queue的習題 1. 最小棧 2. 棧的壓入、彈出序列 3.二叉樹的層序遍歷 三、stack和queue的模擬實現 1.stack的模擬實現 2.queue的模擬實現 前言 棧和隊列是倆種特殊的容器&#xff0c;C在實現棧和隊…

Go Go-Simple-Mail包進行批量SMTP郵件發送

go-simple-mail 包提供了一種簡便的方式來處理和發送郵件。這個包支持保持活動連接、TLS和SSL加密協議,非常適合批量SMTP郵件發送需求。 1、安裝Go-Simple-Mail包 go get -u github.com/xhit/go-simple-mail/v2 2、配置SMTP服務器連接 go-simple-mail包支持多種SMTP服務器…

強達電路營收下滑凈利潤急劇放緩:周轉率驟降,2次因環保被罰

《港灣商業觀察》施子夫 自2022年6月向深交所創業板遞交招股書起&#xff0c;深圳市強達電路股份有限公司&#xff08;以下簡稱&#xff0c;強達電路&#xff09;已收到深交所下發的兩輪審核問詢函&#xff0c;并且公司已于2023年3月31日順利過會。但由于遲遲未提交注冊申請&a…

無實驗數據指導蛋白質定向進化,上海交大洪亮課題組發表微環境感知圖神經網絡 ProtLGN

在現代生物技術和醫藥研究中&#xff0c;蛋白質工程扮演著至關重要的角色。通過修改蛋白質的氨基酸序列&#xff0c;蛋白質工程可以改善或賦予蛋白質新的生物化學性質&#xff0c;如增強酶的催化效率、提高藥物的親和力或改善其熱穩定性。這些改進對于開發新藥、治療疾病以及提…

lua vm 一: attempt to yield across a C-call boundary 的原因分析

使用 lua 的時候有時候會遇到這樣的報錯&#xff1a;“attempt to yield across a C-call boundary”。 1. 網絡上的解釋 可以在網上找到一些關于這個問題的解釋。 1.1 解釋一 這個 issue&#xff1a;一個關于 yield across a C-call boundary 的問題&#xff0c;云風的解釋是…

【最新鴻蒙應用開發】——實用廣告思路,可動態修改(方便運營)

鴻蒙項目加入廣告展示頁業務 廣告頁的思路——華為有廣告業務&#xff0c;但是我們不用- ad模塊&#xff1b; 想自定義廣告——場景&#xff1a; app啟動-有廣告需求&#xff0c;就打開廣告頁&#xff0c;沒有的話就去登錄或者主頁&#xff1b; 騰訊體育的廣告- 啟動有廣告頁…

適合小白學習的項目1894java開發ssm框架校園跑腿管理系統myeclipse開發mysql數據庫springMVC模式java編程計算機網頁設計

一、源碼特點 java ssm 校園跑腿管理系統是一套完善的web設計系統&#xff08;系統采用SSM框架進行設計開發&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;對理解JSP java編程開發語言有幫助&#xff0c;系統具有完整的源代碼和數據庫&#xff0c;系統主要采…

Java項目:96 springboot精品在線試題庫系統

作者主頁&#xff1a;舒克日記 簡介&#xff1a;Java領域優質創作者、Java項目、學習資料、技術互助 文中獲取源碼 項目介紹 這次開發的精品在線試題庫系統有管理員&#xff0c;教師&#xff0c;學生三個角色。 管理員功能有個人中心&#xff0c;專業管理&#xff0c;學生管理…

比較(二)利用python繪制雷達圖

比較&#xff08;二&#xff09;利用python繪制雷達圖 雷達圖&#xff08;Radar Chart&#xff09;簡介 雷達圖可以用來比較多個定量變量&#xff0c;也可以用于查看數據集中變量的得分高低&#xff0c;是顯示性能表現的理想之選。缺點是變量過多容易造成閱讀困難。 快速繪制…

Go語言 一些問題了解

一、讀取文件數據&#xff0c;是阻塞還是非阻塞的&#xff1f; 分兩種情況&#xff1a;常規讀取文件數據&#xff0c;和網絡IO讀取數據 1. 常規讀取文件數據&#xff1a; io.Reader 和 bufio.Reader 是同步進行的。 bufio.Reader 提供緩沖的讀取操作&#xff0c;意味著數據是…

網站入門:Flask用法講解

Flask是一個使用Python編寫的輕量級Web服務框架&#xff0c;旨在幫助開發人員快速構建和部署Web應用程序。下面將對Flask進行更為詳細的解釋說明&#xff0c;并展示其使用示例與注意事項&#xff1a; 1.解釋說明 定義及特點: Flask以其簡潔和靈活著稱&#xff0c;允許開發者以…

C++:list模擬實現

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起學習《C&#xff1a;list模擬實現》&#xff0c;感謝大家對我上一篇的支持&#xff0c;如有什么問題&#xff0c;還請多多指教 &#xff01; 如果本篇文章對你有幫助&#xff0c;還請各位點點贊&#xff01;&#xf…

LeetCode題練習與總結:二叉樹展開為鏈表--114

一、題目描述 給你二叉樹的根結點 root &#xff0c;請你將它展開為一個單鏈表&#xff1a; 展開后的單鏈表應該同樣使用 TreeNode &#xff0c;其中 right 子指針指向鏈表中下一個結點&#xff0c;而左子指針始終為 null 。展開后的單鏈表應該與二叉樹 先序遍歷 順序相同。 …

深入探討Java字符串拼接的藝術

引言 在Java編程中&#xff0c;字符串是最基本的數據類型之一。字符串拼接是開發過程中一個非常常見的操作&#xff0c;無論是構建用戶界面的文本&#xff0c;還是生成日志信息&#xff0c;都離不開字符串的拼接。然而&#xff0c;字符串拼接的效率和正確性常常被開發者忽視&a…

格式化數據恢復指南:從備份到實戰,3個技巧一網打盡

朋友們&#xff01;你們有沒有遇到過那種“啊&#xff0c;我的文件呢&#xff1f;”的尷尬時刻&#xff1f;無論是因為手滑、電腦抽風還是其他原因&#xff0c;數據丟失都可能會讓我們抓狂&#xff0c;甚至有時候&#xff0c;我們可能一不小心就把存儲設備格式化了&#xff0c;…

香橙派OrangePI AiPro測評 【運行qt,編解碼,xfreeRDP】

實物 為AI而生 打開盒子 配置 扛把子的 作為業界首款基于昇騰深度研發的AI開發板&#xff0c;Orange Pi AIpro無論在外觀上、性能上還是技術服務支持上都非常優秀。采用昇騰AI技術路線&#xff0c;集成圖形處理器&#xff0c;擁有8GB/16GB LPDDR4X&#xff0c;可以外接32…

進程通信——管道

什么是進程通信&#xff1f; 進程通信是實現進程間傳遞數據信息的機制。要實現數據信息傳遞就要進程間共享資源——內存空間。那么是哪塊內存空間呢&#xff1f;進程間是相互獨立的&#xff0c;一個進程不可能訪問其他進程的內存空間&#xff0c;那么這塊空間只能由操作系統提…

什么是RPA自動化辦公?

RPA自動化辦公&#xff1a;提升效率的利器 如今&#xff0c;自動化辦公已成為提升效率、減少錯誤、節省成本的關鍵手段。RPA&#xff08;機器人流程自動化&#xff0c;Robotic Process Automation&#xff09;作為其中的重要組成部分&#xff0c;正受到越來越多企業的青睞。那…

【全開源】簡單商城系統源碼(PC/UniAPP)

提供PC版本、UniAPP版本(高級授權)、支持多規格商品、優惠券、積分兌換、快遞鳥電子面單、支持移動端樣式、統計報表等 提供全部前后臺無加密源代碼、數據庫離線部署。 構建您的在線商店的基石 一、引言&#xff1a;為什么選擇簡單商城系統源碼&#xff1f; 在數字化時代&am…

【Spring Cloud Alibaba】初識Spring Cloud Alibaba

目錄 回顧主流的微服務框架Spring Cloud 版本簡介Spring Cloud以往的版本發布順序排列如下&#xff1a; 由停更引發的"升級慘案"哪些Netflix組件被移除了&#xff1f; 替換方案服務注冊中心&#xff1a;服務調用&#xff1a;負載均衡&#xff1a;服務降級&#xff1a…