题解 P2866 【[USACO06NOV]糟糕的一天Bad Hair Day】

Hexarhy · 2020-01-27 15:46:13 · 题解

本题适合刚学单调栈的同学练练手。

解题思路

题目说得挺清楚的。下面是思路。

让你维护一个严格递减的序列，显然是单调栈了。栈也是严格递减的。

与其求一头牛能看见几头牛，不如反过来，计算一头牛能被几头牛看见。由于是要求总数，因此不难想到，能看见的总数一定等于被看见的总数。

当然前者方法肯定也能做出来，这里不展开，或者看看这里。

那么思路就很清晰了，稍稍讨论即可：

设栈顶元素高度为 h，新加进来第 i 个元素高度为 x，ans_i 为第 i 头奶牛被看见的数目。
若 h>x，栈保持严格递减，直接入栈；
否则，即当 h\le x，为保持单调性，出栈，直到满足条件。
计算答案时，对于 x，栈内的所有元素都比它高，ans_i 等于栈的元素个数，即ans[i]=stack.size()。
当然，上一步骤可简化为ans+=stack.size()。毕竟只要求总和。

实现细节

请区分“单调递减”和“严格递减”！前者是包括等号的，而后者不包括等号。因此在判断时，h\le x 都要出栈。
养成好习惯，使用栈前一定要判断栈是否为空。
栈内可以储存下标或高度。这对本题影响不大。下面代码储存下标。
以后求和一个数组时，可以采用std::accumulate()，头文件为<numeric>。详细内容见文末。
养成好习惯：请估算答案是否可能超过int。本题最多共有 n=8\times 10^4 个，因此答案最大为 \frac{n(n-1)}{2}\approx3\times10^9。而int大约为 2\times 10^9，因此需要long long。

参考代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <numeric>//注意头文件
using namespace std;

int n;
stack <int> s;

int main()
{
    cin>>n;
    vector <long long> h(n+5),ans(n+5);//动态开数组，可学可不学。vector默认为0
    for(int i=1;i<=n;i++)
     cin>>h[i];
    for(int i=1;i<=n;i++)
    {
        while(!s.empty() && h[s.top()]<=h[i])
         s.pop();//不满足要求的出栈
        ans[i]=s.size();//第i头能被看见
        s.push(i);
    }
    cout<<accumulate(ans.begin(),ans.end(),0LL)<<endl;//推荐
    return 0;
}

附加：关于`std::accumulate()`

首先，不需要C++11。记住头文件为<numeric>。

std::accumulate(first,last,val,f)：

其中前两个参数是迭代器，用法跟std::sort()一样。

函数意义为，返回一个数值，为区间 [first,last) 中,若每个元素为 x，则 f(x,val) 的和。

当函数中没有f时，默认为[](type a,type b){return a+b;}，即加法运算。

因此，语句accumulate(ans.begin(),ans.end(),0LL)表示long long类型的 \sum ans。

函数的返回值类型取决于参数的类型。

~~更多详细内容可以百度。~~

题解 P2866 【[USACO06NOV]糟糕的一天Bad Hair Day】

解题思路

实现细节

参考代码

附加：关于std::accumulate()

附加：关于`std::accumulate()`