本文分享的必刷題目是從藍(lán)橋云課、洛谷、AcWing等知名刷題平臺精心挑選而來并結(jié)合各平臺提供的算法標(biāo)簽和難度等級進(jìn)行了系統(tǒng)分類。題目涵蓋了從基礎(chǔ)到進(jìn)階的多種算法和數(shù)據(jù)結(jié)構(gòu)旨在為不同階段的編程學(xué)習(xí)者提供一條清晰、平穩(wěn)的學(xué)習(xí)提升路徑。歡迎大家訂閱我的專欄算法題解C與Python實(shí)現(xiàn)附上匯總貼算法競賽備考沖刺必刷題C | 匯總【題目來源】洛谷P1693 [USACO19FEB] Sleepy Cow Herding B - 洛谷luogu.com.cn)【題目描述】Farmer John的三頭獲獎奶牛Bessie、Elsie和Mildred總是會迷路走到農(nóng)場上遙遠(yuǎn)的地方去他需要你幫助將她們一起趕回來。農(nóng)場的草地大體是一塊狹長的區(qū)域——我們可以將其想象成一條數(shù)軸奶?？梢哉紦?jù)數(shù)軸上的任意整數(shù)位置。這3頭奶牛現(xiàn)在正位于不同的整數(shù)位置Farmer John想要移動她們使得她們占據(jù)三個相鄰的位置例如位置6 66、7 77、8 88。不幸的是奶牛們現(xiàn)在很困Farmer John要讓她們集中精力聽從命令移動并不容易。任意時刻他只能使得一頭處在“端點(diǎn)”在所有奶牛中位置最小或最大位置的奶牛移動。當(dāng)他移動奶牛時他可以命令她走到任意一個未被占用的整數(shù)位置只要在新的位置上她不再是一個端點(diǎn)。可以看到隨著時間的推移這樣的移動可以使奶牛們趨向越來越近。請求出使得奶牛們集中到相鄰位置所進(jìn)行的移動次數(shù)的最小和最大可能值?！据斎搿枯斎氚恍邪ㄈ齻€空格分隔的整數(shù)為Bessie、Elsie和Mildred的位置。每個位置均為一個范圍1 … 10 9 1\dots 10^91…109內(nèi)的整數(shù)?！据敵觥枯敵龅牡谝恍邪現(xiàn)armer John需要將奶牛們聚集起來所需進(jìn)行的最小移動次數(shù)。第二行包含他將奶牛聚集起來能夠進(jìn)行的最大移動次數(shù)?！据斎霕永? 7 9【輸出樣例】1 2【核心思想】問題分析給定三頭奶牛在數(shù)軸上的位置每次只能移動端點(diǎn)位置的奶牛到任意未被占用的整數(shù)位置且移動后該奶牛不能仍是端點(diǎn)。求使三頭奶牛占據(jù)三個相鄰位置的最小和最大移動次數(shù)。這是一個分類討論/直接模擬問題關(guān)鍵在于分析三頭奶牛的相對位置間隔根據(jù)間隔大小直接判定最小和最大步數(shù)。算法選擇排序 間隔分析先排序得到a 1 a 2 a 3 a_1 a_2 a_3a1?a2?a3?計(jì)算兩個間隔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?計(jì)算間隔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á)( 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)僅需存儲三個位置分類討論的核心思想端點(diǎn)移動約束只能移動最小或最大位置的奶牛且移動后不能仍是端點(diǎn)這意味著端點(diǎn)奶牛必須移動到中間區(qū)域最小步數(shù)分析若存在間隔為2 22可將中間奶牛或端點(diǎn)奶牛一步移動到間隔處使三者連續(xù)若兩個間隔均≥ 3 \ge 3≥3至少需要2 22步先移動一個端點(diǎn)縮小間隔再調(diào)整最大步數(shù)分析每次只移動一步到相鄰空位最大步數(shù) 較大間隔? 1 - 1?1逐格移動端點(diǎn)向中間靠攏適用于小規(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];}// 對三個位置進(jìn)行排序從小到大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;}【運(yùn)行結(jié)果】4 7 9 1 2