算法合集之信息學(xué)競(jìng)賽中搜索問(wèn)題的常見(jiàn)優(yōu)化技巧(已改無(wú)錯(cuò)字)
2022-11-16 20:30:49 本頁(yè)面
【正文】 …S n} {T0T1T2……T n} s 0 s1 s2 s 3 s 4 t 4 t 3 t 2 t 1 t 0 X 1 X 2 X 3 X 5 X 6 X 7 X 8 X 4 Xi∈ S SiSi1 TiTi1 在搜索中從小到大搜索每個(gè) Si和Ti的位置。 由具體分析 對(duì)于原數(shù)列： 1 1 5 2 5， S=｛ 1,2,4,5｝ 由它得到的值為： 1 2 7 9 14 5 7 12 13 14 排序后為： 1 2 5 7 7 9 12 13 14 14 13 12 9 7 7 5 2 1 原數(shù)列： 1 1 ５ ２ ５ 這樣，對(duì)于這個(gè)數(shù)據(jù)，我們已經(jīng)構(gòu)造出了原數(shù)列。 改變搜索對(duì)象 ? 題目的約束條件集中在 Si和 Ti中，我們改變搜索的對(duì)象，不再搜索原數(shù)列中每個(gè)數(shù)的值，而是搜索給出的數(shù)中出現(xiàn)在 Si或者 Ti中的位置。又由于 Si+1與 Si的約束關(guān)系，提示我們?cè)谒阉髦邪凑?Si中 i遞增或者遞減的順序進(jìn)行搜索。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1