浅析拯救小矮人的 nlogn 算法及其证明
淺析拯救小矮人的 nlogn 算法及其證明
題型簡(jiǎn)介：
有 $ n $ 個(gè)人，第 $ i $ 個(gè)人身高 $ a_i $ 手長(zhǎng) $ b_i $ ，他們?yōu)榱藦囊粋€(gè)高為 $ H $ 的洞中出去，決定搭人梯。如果一個(gè)人和他下面的人的身高之和加上他的手長(zhǎng)可以達(dá)到洞的高度，那么他就可以出去。求最多有多少人能出去。 $ n\leq 10^6 $
算法流程
本題需要貪心，所以我們可以貪心到底。首先我們將所有人，按照他們的最低逃生高度 $ H-a_i-b_i $ 從高到低排序。一個(gè)必須要知道的結(jié)論：最低逃生高度越高的人，一定越先走。
首先我們將所有人按照 $ H-a_i-b_i $ （最低逃生高度）從高到低排序，根據(jù)結(jié)論越高的人越先走。然后如果是 $ n^2 $ 背包，就是對(duì)每個(gè)人做有條件的背包，模擬每個(gè)人是否能走。
而 $ n\times logn $ 的方法則是記錄一個(gè)后綴 $ s[] $ ，其中 $ s[i] $ 表示第 $ i $ 個(gè)人后面最低逃生高度比他低的所有人的身高總和，然后用一個(gè) $ tot $ 記錄前面沒(méi)有出去的人的身高總和，對(duì)于從高到低枚舉的第 $ i $ 個(gè)人，如果 $ s[i]+tot>=H-a_i-b_i $ 就說(shuō)明他能出去（于是默認(rèn)他出去）；否則就將這個(gè)人的身高和前面所有已經(jīng)出去的人的身高作比較，如果當(dāng)前這個(gè)人最高那么他就不出去了，不然就從前面已經(jīng)出去的人里面找到那個(gè)最高的人，把他拉回洞里墊在下面，讓當(dāng)前這個(gè)人出去！照著這個(gè)過(guò)程做我們就能得到最優(yōu)解。
算法證明：
其實(shí)這個(gè)算法只有兩個(gè)待考究的地方，問(wèn)題一：為什么最低逃生高度高的人，一定越先走？這個(gè)問(wèn)題在很多題解里已經(jīng)討論過(guò)了，難以講清，本題不做多講，就用一張圖感性一下：
本算法第二個(gè)問(wèn)題在于這句話： 否則就將這個(gè)人的身高和前面所有已經(jīng)出去的人的身高作比較，如果當(dāng)前這個(gè)人最高那么他就不出去了，墊到下面去；不然就從前面已經(jīng)出去的人里面找到那個(gè)最高的人，把他拉回洞里墊在下面，讓當(dāng)前這個(gè)人出去！為什么把上面最高的那個(gè)人拉下來(lái)，這個(gè)人就一定可以出去了？為什么只取一個(gè)人下來(lái)，我們可不可以拉多個(gè)人下來(lái)，讓當(dāng)前這個(gè)人出去的同時(shí)為后面的人墊高度？這個(gè)我們用兩張圖解讀：
$ code: $
#include<iostream> #include<cstdio> #include<iomanip> #include<algorithm> #include<cstring> #include<cstdlib> #include<ctime> #include<cmath> #include<vector> #include<queue> #include<map> #include<set>#define ll long long #define db double #define rg register intusing namespace std;int n,H; //人數(shù)；陷阱高度 int tot,ans; //之前沒(méi)能逃生的人的身高總和；答案 int s[200005]; // s[i]表示在第i個(gè)人后面逃生的所有人的身高總和，就是后綴和 priority_queue<int> q; //用來(lái)求之前已經(jīng)逃生的人中，身高最高的人struct su{int a,b,h,id; //身高，手長(zhǎng)，最低逃生高度，編號(hào)inline bool operator <(const su &i)const{return h>i.h; //按最低逃生高度，從高到底排序 } //（其實(shí)說(shuō)白了就是逃生能力排序，為了方便理解就詳細(xì)一點(diǎn)） }p[200005]; //存小矮人信息的數(shù)組 peopleinline int qr(){ //快讀register char ch; register bool sign=0; rg res=0;while(!isdigit(ch=getchar()))if(ch=='-')sign=1;while(isdigit(ch))res=res*10+(ch^48),ch=getchar();if(sign)return -res; else return res; }int main(){n=qr();for(rg i=1;i<=n;++i)p[i].a=qr(),p[i].b=qr();H=qr();for(rg i=1;i<=n;++i){p[i].h=H-p[i].a-p[i].b; //最低逃生高度p[i].id=i; //每個(gè)人的編號(hào)}sort(p+1,p+n+1);for(rg i=n;i>=1;--i)s[i]=s[i+1]+p[i+1].a; //s[i]表示在第i個(gè)人后面逃生的所有人堆起來(lái)達(dá)到的高度f(wàn)or(rg i=1;i<=n;++i){if(tot+s[i]>=p[i].h) q.push(p[i].a), ++ans;//如果在他前面不能逃生的人加上在他后面的人堆起來(lái)達(dá)到了他的最低逃生高度，就讓他走else{if(!q.empty()&&q.top()>p[i].a){ //拿出之前最大的身高和他對(duì)比，較大的走tot+=q.top();q.pop(); --ans;q.push(p[i].a); ++ans; //其實(shí)ans根本沒(méi)變，為了高度還原就這樣了} else tot+=p[i].a; //否則這個(gè)就墊到下面去}}printf("%d\n",ans);return 0; }轉(zhuǎn)載于:https://www.cnblogs.com/812-xiao-wen/p/11545341.html
總結(jié)
以上是生活随笔為你收集整理的浅析拯救小矮人的 nlogn 算法及其证明的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
