主要是能分析出这样一个结论:
每个 pop 根据这个元素上面被压过多少个元素, 可以知道他是在前面哪个 pop 之前被 push 的.
根据这些信息可以求得每个 pop 到上一个 pop 之间有多少个 push, 最后求个前缀和即可.
- #include <stdio.h>
- const int maxN=1e6+5;
- int N, g[maxN], h[maxN];
- int main() {
- scanf("%d", &N);
- for (int i = 1; i <= N; ++i) {
- scanf("%d", &g[i]);
- if (g[i]) h[i - g[i]] += 1;
- else h[i] = 1;
- }
- for (int i = 2; i <= N; ++i)
- h[i] += h[i - 1];
- for (int i = 1; i <= N; ++i)
- printf("%d", h[i]);
- puts("");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2737622.html