洗剪吹:N个人排队理发,每个人只能看到更矮的人的头,否则视线被挡住。给定他们的身高,求所有人能看到的人头之和。
4.4常用技巧精选(二)
栈
两种思路,第一种是All nearest smaller values的逆问题,即找到最近的greater or equal值,将两者下标做差。
#include<iostream> #include <stack> using namespace std; #define MAX_N 80000 int N; int h[MAX_N]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%d", h + i); } stack<int> sta; long long ans = 0; for (int i = N - 1; i >= 0; --i) { for (; !sta.empty() && h[sta.top()] < h[i]; sta.pop()); ans += (sta.empty() ? N : sta.top()) - i - 1; sta.push(i); } printf("%lld\n", ans); #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; }
16469445 | hankcs | 3250 | Accepted | 488K | 157MS | C++ | 590B | 2017-01-12 10:31:16 |
另一种是转换思路,求每个人头能被几个人看到。明显只能被比自己高的人看到,用一个严格单调递增的栈维护比自己高的人的身高,将栈的大小累加即得到最终答案。
#include<iostream> #include<stack> using namespace std; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int N, h; scanf("%d", &N); scanf("%d", &h); stack<int> sta; sta.push(h); long long ans; for (int i = 1; i < N; i++) { scanf("%d", &h); while (!sta.empty() && sta.top() <= h) { sta.pop(); } ans += sta.size(); sta.push(h); } printf("%lld\n", ans); #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; }
16469354 | hankcs | 3250 | Accepted | 1052K | 454MS | C++ | 543B | 2017-01-12 09:57:11 |
两种思路都用到了栈,核心代码是类似的,视角不同而已。