上海计算机学会2026年5月月赛C++丙组T4 价格的跨度

价格的跨度

题目描述

给定 $N$ 个整数 $A_1,A_2,\cdots ,A_N$，表示黄金在每天的价格。对每个 $A_i$，请计算并输出它的跨度。

所谓 $A_i$ 的跨度，是指从第 $i$ 天开始，一天一天回溯过去的价格，直到遇到一个严格大于 $A_i$ 的价格为止，在这个过程中经历的天数。如果在过去不存在比 $A_i$ 更高的价格，则数到第一天为止。

输入格式

第一行：一个整数表示 $N$
第二行到第 $N+1$ 行：每行一个整数表示 $A_1,A_2,\dots ,A_N$

输出格式

共 $N$ 行，第 $i$ 行有一个整数，表示 $A_i$ 的跨度。

数据范围

$1\le N\le 500,000$
$1\le A_i\le 1,000,000,000$

样例

输入 #1

5
10
20
30
40
50

输出 #1

1
2
3
4
5

输入 #2

3
314
15
926

输出 #2

1
1
3

题解

这道题要求求出每个位置往前第一个严格更大的数的位置，再计算跨度，数据量最大到 50 万，暴力遍历会超时，所以我选择用单调栈来高效解题。

#include<bits/stdc++.h>
using namespace std;
int n;
// a数组：单调栈，存储价格数值
int a[1000005];
// b数组：和栈一一对应，存储对应价格的下标
int b[1000005];
// len 表示当前栈顶位置，模拟栈指针
int len=0;
int main() {
// 关闭流同步、解绑cin/cout，加速大数据读写
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 读取总天数n
cin>>n;
// 栈底设置一个极大值，作为边界哨兵，保证所有数都能找到前驱
a[0]=1e9+5;
for(int i=1;i<=n;i++){
// 读取第i天的黄金价格
int x;
cin>>x;
// 维护单调递减栈：弹出栈顶所有 <= 当前价格的元素
// 这些元素不可能成为后面元素的"第一个更大值"
while(a[len]<=x){
len—;
}
// 栈顶就是左侧第一个严格大于x的位置，计算跨度并输出
cout<<i–b[len]<<"\\n";
// 当前价格和下标入栈
len++;
a[len]=x;
b[len]=i;
}
return 0;
}

解题思路

• 用数组模拟栈，a[] 存价格，b[] 存对应天数下标，len 为栈顶指针。
• 提前在栈底放一个极大值哨兵 a[0]，避免判空，保证每个数都能找到结果。

• 遍历每一天的价格，不断弹出栈顶小于等于当前价格的元素（它们不再有用）。
• 此时栈顶元素就是左侧第一个严格更大的价格，用当前下标减去栈顶下标，得到跨度并输出。
• 把当前价格和对应下标压入栈，继续处理下一天。