DDOSvoid's Blog

Luogu P2947 [USACO09MAR]Look Up S

发表于 分类于
本文字数： 646 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P2947

求两边第一个大于或者小于自己的数

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <cctype>
#define maxn 1000010
#define gc getchar
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
}

int n;

struct node {
    int p, v;
} st[maxn]; int top; 

int ans[maxn]; 
int main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int v = read();
        while (top && st[top].v < v) ans[st[top].p] = i, --top;
        st[++top].v = v; st[top].p = i; 
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]); 
    return 0;
}