算法合集之回到起點(diǎn)——一種突破性思維-wenkub
2022-12-23 11:31:04 本頁面
【正文】 法 ? 如果當(dāng)前最后一個(gè)區(qū)間的 z值較前一個(gè)區(qū)間小，根據(jù)引理我們合并這兩個(gè)區(qū)間，新的 z值設(shè)定為它們的中位數(shù) i ti 第 1個(gè)區(qū)間 第 2個(gè)區(qū)間 第 3個(gè)區(qū)間 合并，找到新的中位數(shù) 問題二的解決 —— 第一類算法 ? 如果當(dāng)前最后一個(gè)區(qū)間的 z值較前一個(gè)區(qū)間小，根據(jù)引理我們合并這兩個(gè)區(qū)間，新的 z值設(shè)定為它們的中位數(shù) i ti 第 1個(gè)區(qū)間 第 2個(gè)區(qū)間 第 3個(gè)區(qū)間 合并，找到新的中位數(shù) 問題二的解決 —— 第一類算法 ? 選取一個(gè)優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，它可以高效地完成如下任務(wù)： – 集合合并 – 求出該集合的中位數(shù)。 問題二的解決 —— 定義與說明 ? 由于最優(yōu)方案不為一，下文中描述 X是一組最優(yōu)方案的同時(shí)，并不表示最優(yōu)方案一定是X。 問題二的提出 BalticOI2022 13 Sequence改編 ? 給定序列 t1, t2, … , tN，要求構(gòu)建一個(gè)遞增序列 z1 = z2 = … = zN，使得 |t1 z1| + |t2 z2| + … + |tN zN|盡可能小。 1 2 3 4 5 6 1 2 3 4 5 6 離散行 離散列 離散格 問題一的解決 —— 經(jīng)典算法 [1,10] [1,5] [5,10] [1,3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1