第十四屆藍橋杯_省賽B組(C).冶煉金屬

題目如下:

在這里插入圖片描述
拿到題我們來看一下,題目的意思,就是求出N個記錄中的最大最小值,言外之意就是,如果超過了這個最大值不行,如果小于這個最小值也不行,所以我們得出,這道題是一個二分答案的題目,求出分界點。
首先我們輸入 N 個組別,分別輸入a , b 。
我們先討論最小值,我們寫一個binary_min函數,用來二分答案的最小值,記最小值為 ans
首先,左邊界為 1 通過題目我們知道 我們要求的 V在分母上 所以我們最小為1,最大則為當前a(分子)的值
下來我們開始二分,在二分答案中我們應該寫成while(l<r)這樣我們就不用記錄中間的狀態了(下面注釋中會說到), mid=l+r>>1取中值,下來進入主要邏輯,當a/mid(V)<=b的時候,我們可以得出我們現在的值在分界點的左邊,需要將V的值變大,那么就需要將分母上的值(mid)變小,那么我們就需要向左收縮區間令r=mid(這里說明為什么應該為l<r,我們在之前的二分中,左閉右開時,循環的條件為while(l<=r),而這次需要寫成l<r,我們最終要找的是臨界點 所以我們最后需要 l==r 而不是l=r+1)
當寫成while(l<=r)時,錯誤寫法

// 錯誤示例:使用 l <= r 但不記錄答案
int binary_min(int a, int b) {int l = 1, r = a;while (l <= r) {  // 問題1:循環會在 l=r+1 時結束int mid = (l + r) / 2;if (a / mid <= b) {r = mid - 1;  // 問題2:可能錯過正確答案} else {l = mid + 1;}}return l;  // 錯誤:循環結束時 l 可能已超出有效范圍
}

最主要的就是可能會直接跳過最佳的答案,導致答案不正確(采用左閉右閉的寫法時,應該確保每次右邊的邊界都不會被跳過,由于我們的循環條件為l<r)所以我們應該記錄一下右邊界的值
所以應該向右收縮時記錄值

		if (a / mid <= b) {ans = mid;  // 記錄當前有效解r = mid - 1;  // 向左收縮(關鍵:r=mid-1而非r=mid)} else {l = mid + 1;}

正確寫法

int binary_min(int a, int b) {int l = 1, r = a;while (l < r) {int mid = (l + r) >> 1;if (a / mid <= b) {r = mid;  // 保留當前 mid 作為候選} else {l = mid + 1;}}return l;  // 循環結束時 l 即為答案
}

了解了這一原理,下來繼續寫題,我們寫完函數之后試著輸出一下。
在這里插入圖片描述
得到了這樣一組數據,為什么會出現這種呢?因為有三個記錄,每個記錄對應著一個最小值,對于每個 (a, b),滿足條件的 V 可能形成一個區間 [min_V, max_V]。當有多組輸入時,我們需要找到一個公共的 V 范圍,使得所有組的條件都被滿足。
代碼

	ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));

我們每次都會獲得一個V我們要在所有的可能最小值里面選出一個最大的,在所有可能得最大值中選擇一個最小的,以此來滿足公共區間例如在上面的例子中,18已經是最小的值了,所以我們答案可以大于等于18,所以我們需要取這一堆數的最大值,同理
在這里插入圖片描述
獲得了每組數據的最大上限,大的不一定全部滿足,小的一定全部滿足,找到其中的最小值,就是我們最終答案的最大值

AC代碼:

#include <iostream>
#include<limits.h>
#include<algorithm>
using namespace std;
//找最大值
int binary_max(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r+1)>>1;if((a/mid)>=b){l=mid;}elser=mid-1;}return l;
}//找最小值
int binary_min(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r)>>1;if((a/mid)<=b){r=mid;}elsel=mid+1;}return l;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int N;cin>>N;int ans=INT_MIN,ans2=INT_MAX;while(N--){int a,b;cin>>a>>b;ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));}cout<<ans<<" "<<ans2;return 0;
}

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

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

相關文章

??Android 如何查看CPU架構?2025年主流架構有哪些??

在開發安卓應用或選購手機時&#xff0c;了解設備的CPU架構至關重要。不同的架構影響性能、兼容性和能效比。那么&#xff0c;??如何查看安卓設備的CPU架構&#xff1f;2025年主流架構有哪些&#xff1f;不同架構之間有什么區別&#xff1f;?? 本文將為你詳細解答。 ??1.…

飛算 JavaAI 2.0.0:開啟老項目迭代維護新時代

在軟件開發領域&#xff0c;老項目的迭代與維護一直是開發團隊面臨的難題。代碼邏輯混亂、技術棧陳舊、開發效率低下等問題&#xff0c;讓老項目改造猶如一場 “噩夢”。而飛算 JavaAI 2.0.0 版本的正式上線&#xff0c;通過三大核心能力升級&#xff0c;為老項目開發帶來了全新…

Linux初步介紹

Linux是一種開源的類Unix操作系統內核&#xff0c;廣泛應用于服務器、桌面、嵌入式設備等各種計算平臺。它由Linus Torvalds于1991年首次開發&#xff0c;因其穩定性、安全性和靈活性&#xff0c;被全球開發者和企業廣泛采用。 特點&#xff1a; 開放性&#xff08;開源&#…

OneNet + openssl + MQTT

1.OneNet 使用的教程 1.在網絡上搜索onenet&#xff0c;注冊并且登錄賬號。 2.產品服務-----物聯網服務平臺立即體驗 3.在底下找到立即體驗進去 4.產品開發------創建產品 5.關鍵是選擇MQTT&#xff0c;其他的內容自己填寫 6.這里產品以及開發完成&#xff0c;接下來就是添加設…

行為設計模式之Memento(備忘錄)

行為設計模式之Memento&#xff08;備忘錄&#xff09; 前言&#xff1a; 備忘錄設計模式&#xff0c;有點像vmware快照可以回滾&#xff0c;idea的提交記錄同樣可以混滾&#xff0c;流程引擎中流程可以撤銷到或者回滾到某個指定的狀態。 1&#xff09;意圖 在不破壞封裝性的…

動畫直播如何顛覆傳統?解析足球籃球賽事的數據可視化革命

在5G和AI技術快速發展的今天&#xff0c;體育賽事直播正在經歷一場深刻的變革。傳統視頻直播雖然能提供真實的比賽畫面&#xff0c;但在戰術可視化、數據深度和交互體驗方面存在明顯短板。而基于實時數據驅動的動畫直播技術&#xff0c;正通過創新的方式彌補這些不足&#xff0…

二刷蒼穹外賣 day01

nginx nginx反向代理 將前端發送的請求由nginx轉發到后端服務器 好處&#xff1a; 提速&#xff1a;nginx本身可緩存數據 負載均衡&#xff1a;配置多臺服務器&#xff0c;大量請求來臨可均衡分配 保證后端安全&#xff1a;不暴露后端服務真實地址 server{listen 80;server_…

5.2 HarmonyOS NEXT應用性能診斷與優化:工具鏈、啟動速度與功耗管理實戰

HarmonyOS NEXT應用性能診斷與優化&#xff1a;工具鏈、啟動速度與功耗管理實戰 在HarmonyOS NEXT的全場景生態中&#xff0c;應用性能直接影響用戶體驗。通過專業的性能分析工具鏈、針對性的啟動速度優化&#xff0c;以及精細化的功耗管理&#xff0c;開發者能夠構建"秒…

模型訓練-關于token【低概率token, 高熵token】

Qwen團隊新發現&#xff1a;大模型推理能力的提高僅由少數高熵 Token 貢獻 不要讓低概率token主導了LLM的強化學習過程 一 低概率詞元問題 論文&#xff1a;Do Not Let Low-Probability Tokens Over-Dominate in RL for LLMs 在RL訓練過程中&#xff0c;低概率詞元&#xff08…

XCTF-web-easyupload

試了試php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都沒有用 嘗試.user.ini 抓包修改將.user.ini修改為jpg圖片 在上傳一個123.jpg 用蟻劍連接&#xff0c;得到flag

gRPC、WebSocket 與 HTTP 的核心區別對比

gRPC、WebSocket 與 HTTP 的核心區別對比&#xff0c;涵蓋通信模式、協議特性及適用場景&#xff1a; &#x1f504; ?一、通信模式? ?HTTP? ?單向請求-響應?&#xff1a;客戶端發起請求&#xff0c;服務器返回響應后連接立即關閉13。?無狀態協議?&#xff1a;每次請求…

Android第十三次面試總結(四大 組件基礎)

Activity生命周期和四大啟動模式詳解 一、Activity 生命周期 Activity 的生命周期由一系列回調方法組成&#xff0c;用于管理其創建、可見性、焦點和銷毀過程。以下是核心方法及其調用時機&#xff1a; ?onCreate()?? ?調用時機?&#xff1a;Activity 首次創建時調用。?…

講講JVM的垃圾回收機制

垃圾回收就是對內存堆中已經死亡或者長時間沒有使用的對象進行清楚或回收。 JVM 在做 GC 之前&#xff0c;會先搞清楚什么是垃圾&#xff0c;什么不是垃圾&#xff0c;通常會通過可達性分析算法來判斷對象是否存活。 在確定了那些垃圾可以被回收后&#xff0c;垃圾回收器&…

QT軟件外包開發費用

國內QT軟件外包開發費用是一個非常復雜的問題&#xff0c;沒有一個固定的價格&#xff0c;它受到多種因素的影響。以下將詳細闡述影響QT軟件外包開發費用的主要因素&#xff0c;并提供大致的價格區間供參考&#xff08;請注意&#xff0c;這些價格僅為估算&#xff0c;實際報價…

iOS 16 SwiftUI 優雅跳轉實踐:用枚舉路由和 NavigationStack 實現多頁面導航

引言&#xff1a;跳轉的混亂與優雅的必要性 SwiftUI 給我們帶來了聲明式界面的全新開發體驗&#xff0c;但當涉及到頁面跳轉時&#xff0c;許多開發者仍然面臨一些“舊痛”。最初的 NavigationLink(destination:isActive:) 或 sheet(isPresented:) 等方式雖然能用&#xff0c;…

TikTok矩陣養號實戰:住宅IP純凈度與設備指紋聯動方案

在TikTok矩陣運營中&#xff0c;住宅IP純凈度和設備指紋管理是規避風控的核心。以下方案整合多平臺風控邏輯與實戰數據&#xff0c;覆蓋環境隔離、行為模擬到風險防控全流程。 &#x1f527; 一、住宅IP純凈度維持策略 IP篩選與驗證 靜態住宅IP優選&#xff1a;核心賬號綁定目標…

Elasticsearch增刪改查語句

創建索引庫&#xff1a;不帶映射的 PUT /索引名稱 {"settings": {"number_of_shards": 3, // 主分片數"number_of_replicas": 1 // 每個主分片的副本數} } 創建帶映射的索引庫&#xff1a; PUT /products {"settings": {"…

樹莓派4B, ubuntu20.04, 安裝Ros Noetic[踩坑記錄]

一、安裝過程 1. 硬件要求 樹莓派4B (建議4GB或8GB內存版本) 至少16GB的microSD卡 2. 下載并安裝Ubuntu 20.04 Ubuntu 20.04 LTS (Focal Fossa) for Raspberry Pi 使用Raspberry Pi Imager或BalenaEtcher將鏡像寫入microSD卡 3. 安裝ROS Noetic ?# 設置sources.list s…

視覺slam--框架

視覺里程計的框架 傳感器 VO--front end VO的缺點 后端--back end 后端對什么數據進行優化 利用什么數據進行優化的 后端是怎么進行優化的 回環檢測 建圖 建圖是指構建地圖的過程。 構建的地圖是點云地圖還是什么信息的地圖&#xff1f; 建圖并沒有一個固定的形式和算法…

每日算法 -【Swift 算法】刪除鏈表的倒數第 N 個結點

?? Swift | 刪除鏈表的倒數第 N 個結點(含詳細注釋) 在刷算法題時,我們經常會遇到關于鏈表的題目,而「刪除鏈表的倒數第 N 個節點」是其中一個非常經典的題。今天我們就用 Swift 來實現它,并梳理清楚整個思路。 ?? 一、題目描述 給你一個鏈表,刪除鏈表的倒數第 n 個…