【题解】洛谷P1823 [COI2007]Patrik音乐会的等待

题目

洛谷P1823[COI2007]Patrik音乐会的等待

题解

使用单调栈维护一个不严格递减的数列,将新的元素与栈顶元素依次比较,如果符合要求(能互相看到)就计数,同时维护栈内数据的性质。计数时细节较多:题中要求多少对人,所以在对新元素进行处理时,只需要统计他左边能互相看到的人;多个连续的高度相同的人能互相看到;相邻的人能互相看到;相邻且高度相同的人只要统计一次。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月2日 上午9:20

【小白解析】
此题基本沿袭单调栈思路。第15行的else(相当于if(t<s.top().first||!s.size())保证栈内数据单调递减,最先弹出的数据即为当前最小数据,随后依次增大。该操作保证了第13行考察每一个栈成员的second值时,不会出现重复的对——因为先考察的最小成员的身高小于剩余所有成员身高,因而其涉及的对不可能与剩余任意成员的对有交集。
题解剩余的思路便是考察读进的数据身高是否大于栈内的最小数据,若大于,则读进的数据能够与最小数据的所有对话对象进行对话,因此答案加s.top().second。随后弹出最小对象,考察此时的top,直至寻得身高不小于读进数据的对象。若top的身高大于读进对象或栈已空,此时将读进对象自身算作一个可以对话的对象,初始化其second为1,推入栈内。若此时栈内超过两人,说明此时的top有且仅有其左侧1个身高高于他的对话对象,故ans++。
14行右侧的s.top().second++操作,保证ans先加上s.top().second,后s.top().second加1,避免与16行操作重复。
*话说身高相同难道不一样遮挡视野吗……