本文分享的必刷題目是從藍橋云課、洛谷、AcWing等知名刷題平臺精心挑選而來并結(jié)合各平臺提供的算法標(biāo)簽和難度等級進行了系統(tǒng)分類。題目涵蓋了從基礎(chǔ)到進階的多種算法和數(shù)據(jù)結(jié)構(gòu)旨在為不同階段的編程學(xué)習(xí)者提供一條清晰、平穩(wěn)的學(xué)習(xí)提升路徑。歡迎大家訂閱我的專欄算法題解C與Python實現(xiàn)附上匯總貼算法競賽備考沖刺必刷題C | 匯總【題目來源】洛谷P1693 [USACO19FEB] Sleepy Cow Herding B - 洛谷luogu.com.cn)【題目描述】Farmer John的三頭獲獎奶牛Bessie、Elsie和Mildred總是會迷路走到農(nóng)場上遙遠的地方去他需要你幫助將她們一起趕回來。農(nóng)場的草地大體是一塊狹長的區(qū)域——我們可以將其想象成一條數(shù)軸奶牛可以占據(jù)數(shù)軸上的任意整數(shù)位置。這3頭奶?，F(xiàn)在正位于不同的整數(shù)位置Farmer John想要移動她們使得她們占據(jù)三個相鄰的位置例如位置6 66、7 77、8 88。不幸的是奶牛們現(xiàn)在很困Farmer John要讓她們集中精力聽從命令移動并不容易。任意時刻他只能使得一頭處在“端點”在所有奶牛中位置最小或最大位置的奶牛移動。當(dāng)他移動奶牛時他可以命令她走到任意一個未被占用的整數(shù)位置只要在新的位置上她不再是一個端點。可以看到隨著時間的推移這樣的移動可以使奶牛們趨向越來越近。請求出使得奶牛們集中到相鄰位置所進行的移動次數(shù)的最小和最大可能值?！据斎搿枯斎氚恍邪ㄈ齻€空格分隔的整數(shù)為Bessie、Elsie和Mildred的位置。每個位置均為一個范圍1 … 10 9 1\dots 10^91…109內(nèi)的整數(shù)?！据敵觥枯敵龅牡谝恍邪現(xiàn)armer John需要將奶牛們聚集起來所需進行的最小移動次數(shù)。第二行包含他將奶牛聚集起來能夠進行的最大移動次數(shù)?！据斎霕永? 7 9【輸出樣例】1 2【核心思想】問題分析給定三頭奶牛在數(shù)軸上的位置每次只能移動端點位置的奶牛到任意未被占用的整數(shù)位置且移動后該奶牛不能仍是端點。求使三頭奶牛占據(jù)三個相鄰位置的最小和最大移動次數(shù)。這是一個分類討論/直接模擬問題關(guān)鍵在于分析三頭奶牛的相對位置間隔根據(jù)間隔大小直接判定最小和最大步數(shù)。算法選擇排序 間隔分析先排序得到a 1 a 2 a 3 a_1 a_2 a_3a1?a2?a3?計算兩個間隔d 1 a 2 ? a 1 d_1 a_2 - a_1d1?a2??a1?、d 2 a 3 ? a 2 d_2 a_3 - a_2d2?a3??a2?分類討論根據(jù)( d 1 , d 2 ) (d_1, d_2)(d1?,d2?)的不同組合直接輸出對應(yīng)的最小和最大移動次數(shù)關(guān)鍵步驟讀取輸入三個整數(shù)位置排序sort(a1, a4)得到有序位置a 1 , a 2 , a 3 a_1, a_2, a_3a1?,a2?,a3?計算間隔d 1 a 2 ? a 1 d_1 a_2 - a_1d1?a2??a1?d 2 a 3 ? a 2 d_2 a_3 - a_2d2?a3??a2?分類判斷已相鄰d 1 1 d_1 1d1?1且d 2 1 d_2 1d2?1最小 最大 0 00一步可達( d 1 2 (d_1 2(d1?2且d 2 1 ) d_2 1)d2?1)或( d 1 1 (d_1 1(d1?1且d 2 2 ) d_2 2)d2?2)或( d 1 2 (d_1 2(d1?2且d 2 2 ) d_2 2)d2?2)最小 最大 1 11間隔一大一小若d 1 2 d_1 2d1?2且d 2 1 d_2 1d2?1或d 1 1 d_1 1d1?1且d 2 2 d_2 2d2?2最小 2 22若d 1 2 d_1 2d1?2且d 2 2 d_2 2d2?2或d 1 2 d_1 2d1?2且d 2 2 d_2 2d2?2最小 1 11最大 max ? ( d 1 ? 1 , d 2 ? 1 ) \max(d_1 - 1, d_2 - 1)max(d1??1,d2??1)間隔均大于2 22最小 2 22最大 max ? ( d 1 ? 1 , d 2 ? 1 ) \max(d_1 - 1, d_2 - 1)max(d1??1,d2??1)時間/空間復(fù)雜度時間復(fù)雜度O ( 1 ) O(1)O(1)僅排序和若干次比較空間復(fù)雜度O ( 1 ) O(1)O(1)僅需存儲三個位置分類討論的核心思想端點移動約束只能移動最小或最大位置的奶牛且移動后不能仍是端點這意味著端點奶牛必須移動到中間區(qū)域最小步數(shù)分析若存在間隔為2 22可將中間奶?；蚨它c奶牛一步移動到間隔處使三者連續(xù)若兩個間隔均≥ 3 \ge 3≥3至少需要2 22步先移動一個端點縮小間隔再調(diào)整最大步數(shù)分析每次只移動一步到相鄰空位最大步數(shù) 較大間隔? 1 - 1?1逐格移動端點向中間靠攏適用于小規(guī)模約束移動 極值分析類問題核心是通過間隔分類直接得出答案【解題思路】【算法標(biāo)簽】#普及- #模擬【代碼詳解】#includebits/stdc.husingnamespacestd;inta[5];// 存儲三個奶牛的位置intminn0;// 最小移動次數(shù)intmaxn0;// 最大移動次數(shù)// 文件輸入輸出流注釋掉的代碼// ifstream filein(herding.in);// ofstream fileout(herding.out);intmain(){// 輸入三個奶牛的位置for(inti1;i3;i){// cin a[i];// filein a[i];cina[i];}// 對三個位置進行排序從小到大sort(a1,a31);// 情況1三個奶牛已經(jīng)連續(xù)相鄰間隔都為1if(a[2]-a[1]1a[3]-a[2]1){// 無需移動cout0endl0endl;}// 情況2兩個間隔分別為2和1如1,3,4 或 1,2,4elseif((a[2]-a[1]2a[3]-a[2]1)||(a[2]-a[1]1a[3]-a[2]2)){// 只需要移動一次即可使三個奶牛連續(xù)cout1endl1endl;}// 情況3兩個間隔都為2如1,3,5elseif(a[2]-a[1]2a[3]-a[2]2){// 只需要移動一次即可使三個奶牛連續(xù)cout1endl1endl;}// 情況4一個間隔大于2另一個間隔為1如1,4,5 或 1,2,5elseif((a[2]-a[1]2a[3]-a[2]1)||(a[2]-a[1]1a[3]-a[2]2)){minn2;// 最小需要移動2次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移動次數(shù)為較大間隔減1coutminnendlmaxnendl;}// 情況5一個間隔大于2另一個間隔為2如1,4,6 或 1,3,6elseif((a[2]-a[1]2a[3]-a[2]2)||(a[2]-a[1]2a[3]-a[2]2)){minn1;// 最小需要移動1次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移動次數(shù)為較大間隔減1coutminnendlmaxnendl;}// 情況6兩個間隔都大于2如1,5,10elseif(a[2]-a[1]2a[3]-a[2]2){minn2;// 最小需要移動2次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移動次數(shù)為較大間隔減1coutminnendlmaxnendl;}return0;}【運行結(jié)果】4 7 9 1 2