gpt-4-1106-preview· OpenAI WildChat-4.8M (AI2)
[COI2007] Patrik 音乐会的等待 题目描述 $n$ 个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。 队列中任意两个人…
- User
[COI2007] Patrik 音乐会的等待
题目描述
个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。
队列中任意两个人 和 ,如果他们是相邻或他们之间没有人比 或 高,那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
输入格式
输入的第一行包含一个整数 ,表示队伍中共有 个人。
接下来的 行中,每行包含一个整数,表示人的高度,以毫微米(等于 米)为单位,这些高度分别表示队伍中人的身高。
输出格式
输出仅有一行,包含一个数 ,表示队伍中共有 对人可以互相看见。
样例 #1
样例输入 #1
7 2 4 1 2 2 5 1样例输出 #1
10提示
数据规模与约定
对于全部的测试点,保证 每个人的高度 ,。
- Assistant
为了解决这个问题,我们可以使用一个单调栈来辅助计算。单调栈是一种特殊的栈结构,其中的元素保持一定的单调性,本题中我们使用单调递减栈。单调栈可以在 O(n) 时间复杂度内完成所有操作。
我们从队列的起始位置开始遍历,对每个人的身高进行以下操作:
- 比较当前身高与栈顶元素比较。如果当前身高大于栈顶,表示栈中的元素可以看到当前人,但当前人之前不能看到更多的人(因为他们都被当前人挡住了)。
- 弹出栈中所有小于当前身高的元素,并对每一个弹出的元素增加计数(这是因为当前人可以看到所有这些较矮的人,同时这些较矮的人之间也能相互看见)。
- 当栈为空或当前人身高不再大于栈顶时,将当前人的身高推入栈中。
需要注意的是,由于可能会有身高相同的人,因此我们在栈中维护的不单单是身高,还需要维护一个身高相同的人的数量。
具体算法如下:
#include <iostream> #include <stack> #include <utility> using namespace std; int main() { int n; long long s = 0; // 结果可能很大,需要用 long long 类型 stack<pair<int, int>> stk; // 对于每个元素,存储 <身高, 相同身高的人数> cin >> n; for (int i = 0; i < n; i++) { int height; cin >> height; pair<int, int> person = {height, 1}; // 初始相同身高的人数为 1 // 弹出所有比当前人矮的人 while (!stk.empty() && stk.top().first <= person.first) { s += stk.top().second; // 对于每一个被弹出的人,他们都可以看到当前人 // 如果高度相同,则需要合并计数 if (stk.top().first == person.first) { person.second += stk.top().second; } stk.pop(); } // 如果栈不为空,则表示当前人至少还能看到栈顶的这个人 if (!stk.empty()) { s++; } // 把当前人的身高和计数推入栈中 stk.push(person); } cout << s << endl; return 0; }这段代码实现了上面的算法,将每个人能够相互看到的情况进行了计数。最终输出
s即为所有成对能够互相看到的人数。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.