Skip to content
The Chat Archive
gpt-4-1106-preview· OpenAI WildChat-4.8M (AI2)

[COI2007] Patrik 音乐会的等待 题目描述 $n$ 个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。 队列中任意两个人…

  1. User

    [COI2007] Patrik 音乐会的等待

    题目描述

    nn 个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。

    队列中任意两个人 aa 和 bb,如果他们是相邻或他们之间没有人比 aa 或 bb 高,那么他们是可以互相看得见的。

    写一个程序计算出有多少对人可以互相看见。

    输入格式

    输入的第一行包含一个整数 nn,表示队伍中共有 nn 个人。

    接下来的 nn 行中,每行包含一个整数,表示人的高度,以毫微米(等于 10−910^{-9} 米)为单位,这些高度分别表示队伍中人的身高。

    输出格式

    输出仅有一行,包含一个数 ss,表示队伍中共有 ss 对人可以互相看见。

    样例 #1

    样例输入 #1

    7 
    2 
    4 
    1 
    2 
    2 
    5 
    1
    

    样例输出 #1

    10
    

    提示

    数据规模与约定

    对于全部的测试点,保证 1≤1\le 每个人的高度 <231< 2^{31},1≤n≤5×1051 \le n \le 5\times 10^5。

  2. Assistant

    为了解决这个问题,我们可以使用一个单调栈来辅助计算。单调栈是一种特殊的栈结构,其中的元素保持一定的单调性,本题中我们使用单调递减栈。单调栈可以在 O(n) 时间复杂度内完成所有操作。

    我们从队列的起始位置开始遍历,对每个人的身高进行以下操作:

    1. 比较当前身高与栈顶元素比较。如果当前身高大于栈顶,表示栈中的元素可以看到当前人,但当前人之前不能看到更多的人(因为他们都被当前人挡住了)。
    2. 弹出栈中所有小于当前身高的元素,并对每一个弹出的元素增加计数(这是因为当前人可以看到所有这些较矮的人,同时这些较矮的人之间也能相互看见)。
    3. 当栈为空或当前人身高不再大于栈顶时,将当前人的身高推入栈中。

    需要注意的是,由于可能会有身高相同的人,因此我们在栈中维护的不单单是身高,还需要维护一个身高相同的人的数量。

    具体算法如下:

    #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 即为所有成对能够互相看到的人数。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.