网站国际化,西安seo外包费用,网站专门做冻品的,网站设计器浅析拯救小矮人的 nlogn 算法及其证明 题型简介#xff1a; 有 $ n $ 个人#xff0c;第 $ i $ 个人身高 $ a_i $ 手长 $ b_i $ #xff0c;他们为了从一个高为 $ H $ 的洞中出去#xff0c;决定搭人梯。如果一个人和他下面的人的身高之和加上他的手长可以达到洞的高度 有 $ n $ 个人第 $ i $ 个人身高 $ a_i $ 手长 $ b_i $ 他们为了从一个高为 $ H $ 的洞中出去决定搭人梯。如果一个人和他下面的人的身高之和加上他的手长可以达到洞的高度那么他就可以出去。求最多有多少人能出去。 $ n\leq 10^6 $ 算法流程 本题需要贪心所以我们可以贪心到底。首先我们将所有人按照他们的最低逃生高度 $ H-a_i-b_i $ 从高到低排序。一个必须要知道的结论最低逃生高度越高的人一定越先走。 首先我们将所有人按照 $ H-a_i-b_i $ 最低逃生高度从高到低排序根据结论越高的人越先走。然后如果是 $ n^2 $ 背包就是对每个人做有条件的背包模拟每个人是否能走。 而 $ n\times logn $ 的方法则是记录一个后缀 $ s[] $ 其中 $ s[i] $ 表示第 $ i $ 个人后面最低逃生高度比他低的所有人的身高总和然后用一个 $ tot $ 记录前面没有出去的人的身高总和对于从高到低枚举的第 $ i $ 个人如果 $ s[i]totH-a_i-b_i $ 就说明他能出去于是默认他出去否则就将这个人的身高和前面所有已经出去的人的身高作比较如果当前这个人最高那么他就不出去了不然就从前面已经出去的人里面找到那个最高的人把他拉回洞里垫在下面让当前这个人出去照着这个过程做我们就能得到最优解。 算法证明 其实这个算法只有两个待考究的地方问题一为什么最低逃生高度高的人一定越先走这个问题在很多题解里已经讨论过了难以讲清本题不做多讲就用一张图感性一下 本算法第二个问题在于这句话 否则就将这个人的身高和前面所有已经出去的人的身高作比较如果当前这个人最高那么他就不出去了垫到下面去不然就从前面已经出去的人里面找到那个最高的人把他拉回洞里垫在下面让当前这个人出去为什么把上面最高的那个人拉下来这个人就一定可以出去了为什么只取一个人下来我们可不可以拉多个人下来让当前这个人出去的同时为后面的人垫高度这个我们用两张图解读 $ code: $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;int n,H; //人数陷阱高度
int tot,ans; //之前没能逃生的人的身高总和答案
int s[200005]; // s[i]表示在第i个人后面逃生的所有人的身高总和就是后缀和
priority_queueint q; //用来求之前已经逃生的人中身高最高的人struct su{int a,b,h,id; //身高手长最低逃生高度编号inline bool operator (const su i)const{return hi.h; //按最低逃生高度从高到底排序 } //其实说白了就是逃生能力排序为了方便理解就详细一点
}p[200005]; //存小矮人信息的数组 peopleinline int qr(){ //快读register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}int main(){nqr();for(rg i1;in;i)p[i].aqr(),p[i].bqr();Hqr();for(rg i1;in;i){p[i].hH-p[i].a-p[i].b; //最低逃生高度p[i].idi; //每个人的编号}sort(p1,pn1);for(rg in;i1;--i)s[i]s[i1]p[i1].a; //s[i]表示在第i个人后面逃生的所有人堆起来达到的高度for(rg i1;in;i){if(tots[i]p[i].h) q.push(p[i].a), ans;//如果在他前面不能逃生的人加上在他后面的人堆起来达到了他的最低逃生高度就让他走else{if(!q.empty()q.top()p[i].a){ //拿出之前最大的身高和他对比较大的走totq.top();q.pop(); --ans;q.push(p[i].a); ans; //其实ans根本没变为了高度还原就这样了} else totp[i].a; //否则这个就垫到下面去}}printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/812-xiao-wen/p/11545341.html
