Ex3-23 亲兄弟问题

« 问题描述：

给定n 个整数0 1 1 , , , n- a a  a 组成的序列。序列中元素i a 的亲兄弟元素k a 定义为：

min{ | } k i j n j j i a = a a ³ a

< <

。

亲兄弟问题要求给定序列中每个元素的亲兄弟元素的位置。元素i a 的亲兄弟元素为k a

时，称k 为元素i a 的亲兄弟元素的位置。当元素i a 没有亲兄弟元素时，约定其亲兄弟元素

的位置为-1。

例如，当n=10，整数序列为6，1，4，3，6，2，4，7，3，5 时，相应的亲兄弟元素位

置序列为：4，2，4，4，7，6，7，-1，9，-1。

« 编程任务：

对于给定的n个整数0 1 1 , , , n- a a  a 组成的序列，试用抽象数据类型栈，设计一个O(n)

时间算法，计算相应的亲兄弟元素位置序列。

« 数据输入：

由文件input.txt提供输入数据。文件的第1 行有1 个正整数n，表示给定给n个整数。

第2 行是0 1 1 , , , n- a a  a 。

« 结果输出:

程序运行结束时，将计算出的与给定序列相应的亲兄弟元素位置序列输出到output.txt

中。

输入文件示例 输出文件示例

input.txt

10

4 2 4 4 7 6 7 -1 9 -1

output.txt

6 1 4 3 6 2 4 7 3 5