P2947 [USACO09MAR] Look Up S
题目描述
约翰的奶牛们站成一排,从左往右依次编号为 1,2,…,n,第 i 头奶牛的身高为 hi。
现在每头奶牛都在向右看。对于奶牛 i 和奶牛 j,若 i<j 且 hi<hj,则称奶牛 i 可以仰望奶牛 j。
请对每头奶牛求出它最近的仰望对象。具体地,奶牛 i 的仰望对象是满足 j>i 且 hj>hi 的最小的 j;若不存在这样的 j,则奶牛 i 没有仰望对象。
输入格式
第一行输入一个整数 n(1≦n≦105) 代表奶牛的数量。
此后 n 行,第 i 行输入一个整数 hi(1≦hi≦106) 代表第 i 头奶牛的身高。
输出格式
输出 n 行,第 i 行输出一个整数,代表奶牛 i 的最近的仰望对象的编号;若奶牛 i 没有仰望对象,则输出 0。
测试样例
6
3
2
6
1
1
2
3
3
0
6
6
0
样例 1 解释
这 6 头奶牛的身高依次为 3,2,6,1,1,2,逐头奶牛分析如下:
∙奶牛 1 的身高为 3。奶牛 2 的身高为 2,并不比它高;奶牛 3 的身高为 6,比它高。因此奶牛 1 最近的仰望对象是奶牛 3;
∙奶牛 2 的身高为 2。奶牛 3 的身高为 6,比它高,因此最近的仰望对象是奶牛 3;
∙奶牛 3 的身高为 6。它右侧的奶牛身高都不超过 6,没有仰望对象;
∙奶牛 4 的身高为 1。奶牛 5 的身高为 1,并不比它高;奶牛 6 的身高为 2,比它高,因此最近的仰望对象是奶牛 6;
∙奶牛 5 的身高为 1。奶牛 6 的身高为 2,比它高,因此最近的仰望对象是奶牛 6;
∙奶牛 6 的身高为 2。它右侧没有奶牛,没有仰望对象。
因此答案为 3,3,0,6,6,0。
5
4
1
3
3
5
5
3
5
5
0
样例 2 解释
这 5 头奶牛的身高依次为 4,1,3,3,5:
∙奶牛 1 仰望奶牛 5,因为奶牛 2,3,4 都不比它高,而奶牛 5 比它高;
∙奶牛 2 仰望奶牛 3,因为奶牛 3 是它右侧第一头比它高的奶牛;
∙奶牛 3 与奶牛 4 身高相同,都不满足“比它高”,因此奶牛 3 仰望奶牛 5;
∙奶牛 4 同样仰望奶牛 5;
∙奶牛 5 右侧没有奶牛,没有仰望对象。
提示
对于 20% 的数据,1≦n≦10。
对于 50% 的数据,1≦n≦103。
对于 100% 的数据,1≦n≦105,1≦hi≦106。