POJ-3250 : Bad Hair Day
問題概要
長さn(<8*10^4)の数列xが与えられる(x[n]=infとする)。各iについて(min j s.t. i
解法
All nearest smaller valuesという有名問題。
acceptされたコード
#include <cstdio> #include <vector> using namespace std; typedef long long int64; const int MAX_N = 80000; int N; int hs[MAX_N], nxtLarger[MAX_N]; void init() { scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%d", hs + i); } } int64 solve() { vector<int> stack; stack.reserve(N); for (int i = N - 1 ; i >= 0; --i) { for (;!stack.empty() && hs[stack.back()] < hs[i]; stack.pop_back()) ; nxtLarger[i] = stack.empty() ? N : stack.back(); stack.push_back(i); } int64 ans = 0; for (int i = 0; i < N; ++i) { ans += (nxtLarger[i] - i - 1); } return ans; } int main() { init(); printf("%lld\n", solve()); return 0; }