二分法

来源:http://www.cnblogs.com/detrol/archive/2017/09/17/7533574.html
-Advertisement-
Play Games

最近做了幾道關於二分法的題目,覺得比較典型,因此拿出來說一說。 首先,先把題目分享一下。 題目描述:上題中講了一個故事,故事大意不用過多關註,有用部分為:某地主有一個大糧倉,這個糧倉容量為 n 個單位,但這個糧倉有個小口,每天會有一部分麻雀過來偷吃糧食,同時地主每天也會從別的地方運來糧食填補。開始的 ...


最近做了幾道關於二分法的題目,覺得比較典型,因此拿出來說一說。

首先,先把題目分享一下。


題目描述:上題中講了一個故事,故事大意不用過多關註,有用部分為:某地主有一個大糧倉,這個糧倉容量為 n 個單位,但這個糧倉有個小口,每天會有一部分麻雀過來偷吃糧食,同時地主每天也會從別的地方運來糧食填補。開始的時候糧倉是滿的,麻雀偷吃和運量的具體信息如下:

1⃣️從第一天開始,每天會有麻雀過來吃糧食,第 i 天會來 i 只麻雀,每隻麻雀吃一個單位的糧食。

2⃣️從第二天開始,地主每天會從別的地方運來 m 個單位的糧食加入到糧倉中,由於糧倉的總容量是 n ,因此運來的糧食填滿糧倉後多餘的糧食扔掉。

題目要求,求出第幾天糧倉第一次空了。

 

針對這個過程舉例如下

上文意思是:假設糧倉容量 n 為 5 ,每天運糧數量為 2 ,那麼

開始之前,糧倉里有5 個單位的糧食,糧倉是滿的。

第一天 ,來了一隻麻雀,吃了 1 單位的糧食,因此在第一天結束的時候,糧倉里剩餘4單位的糧食。

第二天,地主先運來 2 單位的糧食來填補糧倉,由於 n = 5 ,第一天剩餘 4 ,現在運來  2 單位,所以 添進糧倉 1 單位後,有1 單位浪費掉。此時糧倉里有 5 單位的糧食(糧倉是滿的)。填充完畢後,來了 2 只麻雀,吃掉 2 個單位的糧食,此時糧倉里剩餘 3 個單位的糧食。

第三天,地主又運來 2 單位的糧食,將只有 3 個單位糧食的糧倉再次填滿,這次沒有浪費,填充完畢,飛來 3 只麻雀,吃掉 3 單位的糧食,此時糧倉里剩餘 2  個單位的糧食。

第四天,地主運來 2 個單位的糧食,加入 原來剩餘 2 單位糧食後,這時,糧倉里只有 4 單位的糧食,沒有填滿。填充完畢,飛來 4 只麻雀,吃掉 4 個單位的糧食,這時候糧倉空了。

因此,答案即為 4 。

 

題目的輸入輸出格式以及測試數據如下

請務必認真仔細的記住題目中所給的數據範圍。

 


 

根據題目的介紹,可以發現,這道題首先可以分成兩種情況,

1⃣️ n < m 時,第一天 ,1 只麻雀吃過後剩 n - 1 糧食,第二天開始,運來 m 單位的糧食,將糧倉填滿為 n ,第二天結束, 2 只麻雀吃過後剩 n - 2 糧食,在第三天開始時,運來的m糧食又將 糧倉填滿為 n ,。 。 。直到 第 n - 2 的時候,n - 2 只麻雀吃過後,剩餘 2 糧食,第 n - 1 天開始時,運來 m 單位糧食( m > n ),因此又將糧倉填滿為 n ,飛來 n - 1 只麻雀,吃過後,糧倉 剩餘 1 糧食,第 n 天開始,地主運來的 m 單位糧食又把糧倉填滿了,這時飛來 n 只麻雀,正好吃完了 n 單位糧食,因此糧倉就空了 ,(題目要求一旦糧倉空了,就停止計算,不給地主接下來一天運來糧食的機會)由此可以看出,在這種情況中,糧倉吃空需要的天數就是糧倉的總容量 n 。

2⃣️ n > m 時,在前 m 天,麻雀吃掉的糧食都能在第二天的時候補上,但到第 m + 1 天的時候,麻雀吃掉 m + 1糧食,在第 m + 2 的時候運來的 m 糧食 無法將 糧倉填滿。也就是說,從第 m + 1 天開始,第 i 天糧倉的存糧數目在前一天的基礎上減少 i 個單位,假設 在 第 m + k 天將糧食吃完了,那麼從 第 m + 1 天開始計算,在 第 m +k - 1天結束的時候,就滿足 

(1+m) + (2+m) + (3+m) +。。。+(k-1+m)+ < (n-m) +(k-1)*m,

在 第m + k 天結束的時候,就滿足

(1+m)+(2+ m)+。。。+(k+m)>=(n-m)+k*m。

 


 

現在,可以將這個過程進行進一步化簡:

在m天之後,假設加完糧食後糧倉現在有糧食 x 個單位,天數是第 m + i 天,現在把整個糧倉分為兩部分,一部分有糧食 m單位,另一部分有糧食 x-m 個單位,把飛來的 麻雀也分為兩部分,一部分 有麻雀 m 只,另一部分 有麻雀 i 只,要求 m 只麻雀吃 m 個糧食的那部分,i 只麻雀去吃 x-m 的那部分糧食,那麼m只麻雀 每天總能 和運來的 m 單位糧食相抵消,剩餘的 x-m 那部分糧食會不斷減少,直至吃光。也就意味著在 m+1到 m+i 這 i 天,每天 除去 m只剩餘的麻雀 加起來吃掉的就是第 m 天 結束的時候 剩餘的那部分糧食。m天結束的時候剩餘的糧食為 n-m ,

假設在第 m+k 天時候來的麻雀吃光了剩餘的糧食。因此除去每天抵消的那部分,剩餘的麻雀吃到糧食的總數為 n-m。有等式如下

1+2+3+。。。+k >= n - m ,

(這裡用  >=  的原因是,在第 m +k 天的時候,不一定所有來的麻雀都剛好有糧食吃,因此麻雀數有可能比剩餘糧食數多)

並且,在 k-1天的時候,來的麻雀並沒有將剩餘的糧食吃完。滿足

1+2+3 。。。+(k-1)< n-m .

 

之所以要將方法進一步精簡的原因是,題目給的測試數據 是 long long ,第一種方法多加的 k 個m 增大了數據,是有可能導致爆掉 long long 的一個原因。反觀第二種思路,數據減小了不少,會減小這個風險,但是本質上來講是沒有區別的,因為他們是屬於同一量級的數據

第一種思路 不等式左邊為

(1+m)+(2+ m)+。。。+(k+m)=k*m+(1+k)*k/2=k*m+k/2+k*k/2(包含k的二次方項)

第二種思路不等式左邊為

1+2+3+。。。+k =(1+k)*k/2=k/2+k*k/2(同樣包含k的二次方項)

由於 天數 m 和 n 都是 long long 類型的,那麼 k 也必然是 long long 類型的,如果數據給的是 long long 的上限,那麼,二次方必然會超出上界。而且,做為一組優秀的測試數據,應該包含這樣的邊界數據來檢測程式的穩定性。

採用上面的判斷條件來找 k ,只要數據足夠大,閉著眼睛也能將 long long 爆掉,那是不是就意味著 這個方法行不通呢?並非如此,上面的思路是非常精簡的一個思路了。那就在 k 的數據範圍上做文章,k 的最大範圍肯定是 大於1 而小於 n+m 的,假設 m 和 n 的數據為 1e18 量級,那麼加和之後 數據為1e19 量級,由不等式 (1+k)*k/2=k/2+k*k/2=1+2+3+。。。+k >= n - m 可知,k*k 的數據為1e19 的量級的,則 k的量級最大界限變為 1e10。這樣就穩了。

 

既然選對了方向,接下來就是 找這個 k 值了,最簡單的想法是加一層迴圈從第一天到第 n+m 天逐個判斷是否滿足條件,直到找到答案。o(n*n)的時間複雜度,在1e18這樣量級的數據,超時是肯定的,因此找 k 的方法也需要改進。

 

由上面的描述的可以發現在 m +k 天之前,麻雀沒有將 剩餘糧食吃完,而在 m+k 天之後,肯定能將糧食吃完,並且,越往後,吃不到糧食的麻雀越多。得出的規律為:越靠近 m+k 這一天,剩餘的糧食或者吃不到糧食的麻雀會越少。當然,題目要求只考慮 m +k 天及之前的情況,不考慮 m+k 天之後,因此只需要考慮的特征就是 越靠近 m +k 這一天糧食剩餘數越少這一特征。

其次麻雀每天增長的數量有線性的關係,因此 如果 第 i 天麻雀沒吃完,那麼可以肯定 i 天之前,麻雀一定沒有將糧食吃完,那就不用判斷 i天之前的情況了。同樣,如果 第 i 天 麻雀已經將糧食吃完了,那麼在 i 天之後,麻雀一定能將糧食吃完,也不用考慮 i 天之後的情況。現在就需要每次找一個 測試的值 i ,將區間一分為二,在滿足條件的那一半尋找。那麼這個測試值取多少合適呢,經實踐發現,每次將區間等分查找的效率最高,

即 i 取 (左邊界+右邊界)/2。這就是著名的 二分思想。時間複雜度是o(log n)的。

 


 

具體代碼實現有興趣的請打開網頁 http://paste.ubuntu.com/24268046/。

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Hibernatede 一對多映射配置 以公司和員工為例:公司是一,員工是多 第一步 創建兩個實體類,公司和員工 寫核心配置文件hibernate.cfg.xml 寫映射配置文件Company.hbm.xml 和Worker.hbm.xml 第二步 讓兩個實體類之間互相表示 (1)在公司實體類裡面表 ...
  • 概要 golang 的包管理一直沒有官方統一的解決方案,因此也產生了很多非官方的包管理工具。 之前我一直使用的 gb() 能夠很好的隔開各個 golang 工程,當時 gb 創建的工程不太融入已有的 GOPATH 中。 gb 相當於是把工程的目錄作為 GOPATH,並且它的 vendor 目錄也和 ...
  • 1、創建用戶 adduser '用戶名' 2、由root用戶進入到其他用戶的終端 su nannanbin 這裡需要註意,有一些命令可能是root許可權才能使用的,這個時候切換成普通用戶的時候,可能會導致這些命令用不了。 3、ls 展示當前目錄下的文件列表,只是展示文件的名稱而已 當然如果你想要看每個 ...
  • 本文地址:http://www.cnblogs.com/aiweixiao/p/7535351.html 歡迎關註我的微信公眾號哈 “ 程式員的文娛情懷” http://t.cn/RotyZtu 【背景】:由於 file函數是一次性將所有內容讀入記憶體,而php為了防止一些寫的比較糟糕的程式占用太多的 ...
  • 博客園是個非常好的學習知識的地方,相信有很多人跟我一樣,園齡3年,從博客園不知道拷了多少代碼,看了多少博客,自己卻一篇博客都沒寫過。真是罪過。 這次準備寫幾篇關於這個項目源碼的閱讀和理解的文章,大家一起相互學習學習,我可能不會單單就寫源碼一類的東西,還會做很多擴展,比如新的c++的語法,其他的一些工 ...
  • 1 異常概述 2 異常體系 3 異常的原理 4 異常對象的拋出 5 自定義異常&異常類的拋出(throws) 6 異常的分類 7 throw和throws的區別? 8 異常的捕獲 9 異常處理的原則 10 異常的註意事項 ...
  • 簡介 網路無處不在,移動互聯時代也早已到來,單機版程式慢慢的已沒有生命力,所有的程式都要能夠訪問網路,比如 QQ 網路聊天程式、迅雷下載程式等,這些程式都要同網路打交道,本次將與各位小伙伴們分享的就是 Java 中的網路編程—— Socket 通信。 網路基礎知識 兩台電腦要通過網路進行通信,必須 ...
  • 一、添加 devtools 依賴 當配置了 devtools 後,我們在classpath修改任何文件項目都將會自動重啟。 (1)某些資源在更改時不一定需要觸發重新啟動。例如, Thymeleaf 模板可以就地進行編輯。預設情況下更改資源路徑包括了:/META-INF/maven, /META-IN ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...