【算法】POJ 3250 Bad Hair Day

解题思路

将每头牛加入单调栈,记录每次pop操作后栈的长度,也就是每头牛能被多少牛看到,累加之后与每头牛能看到的牛的数量之和一致。
题目里\(1<=n<=80,000\),如果牛的身高序列单调递减,结果最大为\(79999+79998+...+1=79999*80000/2\approx 3.2*10^9\),超出了int的范围,需要用long long

AC代码

#include <iostream>
#include <stack>

int main() {
    int n;
    std::cin >> n;
    std::stack<int> stack;
    int cow;
    std::cin >> cow;
    stack.push(cow);
    long long res = 0;
    for (int i = 1; i < n; i++) {
        std::cin >> cow;
        while (!stack.empty() && stack.top() <= cow) {
            stack.pop();
        }
        res += stack.size();
        stack.push(cow);
    }
    std::cout << res << std::endl;
    return 0;
}
上一篇:一篇不错的文章,可以学习下


下一篇:/bin/bash^M: bad interpreter: No such file or directory”