題意
有n個(gè)房屋一字排開结澄，并從左至右編號(hào)為1, 2, ..., n朴沿。有k個(gè)人陸續(xù)入住，每個(gè)人會(huì)挑選無人住的房屋刨沦，如果有多間可以選擇诗宣，那么選擇離已有人住的房屋最遠(yuǎn)的那一間(不是總距離最遠(yuǎn)哦)，如果還有多個(gè)選擇想诅，選擇編號(hào)最小的召庞。
第一個(gè)人永遠(yuǎn)會(huì)住進(jìn)第一間，問最后一個(gè)人會(huì)住進(jìn)哪間屋子来破。
題解
顯然第2個(gè)人會(huì)住進(jìn)最后一間篮灼，算是一個(gè)特例，在這之后徘禁，有人住的屋子會(huì)把剩余的分成多個(gè)區(qū)間诅诱，下一個(gè)人入住時(shí)，會(huì)選擇一個(gè)區(qū)間中間的房屋入住送朱。
解這題的時(shí)候繞了很多彎路娘荡，比如一開始試圖找到一個(gè)優(yōu)雅的公式去解題，比如像二分一樣驶沼，若有a個(gè)人要在一個(gè)區(qū)間里選房子住炮沐，第一個(gè)一定是住中間，然后區(qū)間被分為兩個(gè)回怜，剩余的人先左邊住1個(gè)大年，右邊住一個(gè)，再左邊住兩個(gè)玉雾，右邊住兩個(gè)翔试，再左邊住四個(gè)……這樣就能確定最后一個(gè)人會(huì)住進(jìn)哪一邊，并且有幾個(gè)人也選擇了那一側(cè)复旬，再縮小范圍繼續(xù)算垦缅，結(jié)果發(fā)現(xiàn)有很多意外情況，加了各種if else后驹碍，才發(fā)現(xiàn)這個(gè)思路就不對壁涎。
后來還是用一個(gè)很暴力直接的方法過了這題柏蘑，而且不慢也不復(fù)雜，至少比上面的各種if else還要優(yōu)雅：
- 每次入住的時(shí)候粹庞，假設(shè)現(xiàn)在有x個(gè)區(qū)間，因?yàn)橄胝乙粋€(gè)離別人盡量遠(yuǎn)的洽损，所以一定會(huì)選擇
(x+1)/2盡量大的區(qū)間(為什么不是x庞溜？這是個(gè)坑，你想想)碑定，如果有多個(gè)流码，就選擇編號(hào)最小的
- 入住之后，區(qū)間會(huì)被分成兩個(gè)(除非原區(qū)間長度小于等于2)延刘，所以任意時(shí)刻漫试，區(qū)間的長度最多四種。
- 按照區(qū)間的長度歸類碘赖，每次可以批量讓一群人入住到一種長度的區(qū)間中驾荣，每個(gè)區(qū)間住一個(gè)，這樣區(qū)間的數(shù)量成指數(shù)級(jí)增長普泡，很快人就都能住完播掷。
- 如果將區(qū)間分為左右兩種后，再分別按3歸類撼班，那么最后就能判斷出最后一個(gè)人進(jìn)入了哪邊的區(qū)間歧匈，且還有幾個(gè)人進(jìn)入了那邊的區(qū)間，遞歸砰嘁。
