FJUT第三周寒假作业《第九集,离间计》栈

时间:2022-04-12 02:19:45

第九集,离间计

TimeLimit:1000MS  MemoryLimit:128MB
64-bit integer IO format:%I64d
 
Problem Description

  拥有了超强的体能和跑步速度后,小A的信心极度膨胀。正当他准备潜入特工们的聚会地点套取情报的时候,小A发现组织的守卫非常严密,根本没有漏洞可钻。最后小A只得返回宾馆同小C商量。

通过小C,小A知道了特工组织内有着严谨的等级排名制度,然而这等级并不是严格按照能力来排的,但可怜的特工们并不全都知道。聪明的小A立马想到了离间计,即通过某种方式告知每个特工那些排名比他高但能力比他低的人,刺激低等级的特工去试探高等级的特工,让他们明白后从而引起内乱,但又担心排名相距太大,低排名的特工会因畏惧而连基本的试探也不敢去,毕竟低等级的特工长期处在高等级的特工的淫威下嘛。(不明白小A为什么会知道该组织内部的等阶排名吗?因为小C曾是该组织的内部高层人员…)

现在给出一个序列,序列中的第i个值表示排名为i的特工的能力值,要求求出每个特工的排名前面第一个比他的能力值小的特工的排名,最高排名从0开始,如果不存在,则输出-1

在成功的离间了部分的特工,小A才能更加容易的潜入特工中获取情报、

Input

多组测试数据。

第一行输入一个整数n(0<n<=100000)

接下来有n个数ai(0<=ai<=1000000).ai表示排名为i的员工的能力值(0<=i<n)。

Output

输出n个数,分别表示每个排名为i(0<=i<n)的特工排在其前面且能力值小于他的特工的排名.

SampleInput
1
5
5
1 2 3 4 5
SampleOutput
-1
-1 0 1 2 3

n=100W常规遍历,那么每次都要遍历一次,那么复杂度达到O(n2)直接超时,于是我们进行优化。

假设序列为 3 1 2 5 4

遍历到1时,那么之后不论什么情况,能力值最小的特工必定是1,而不可能是3,那么3就可以丢掉了。

于是我们猜想用一个递增序列储存储存下可能是答案的特工。不可能是答案的丢掉。那么我们就想到了栈。然后看一段推到过程。序列表示当前栈元素。

FJUT第三周寒假作业《第九集,离间计》栈

结论:1,当栈空,答案为-1

   2,当新元素大于栈顶,答案就是栈顶元素的编号。

   3,新元素小于栈顶,那么意味着栈顶已经失去作用了。弹出。继续比较。之后的结果只有两个,结论1和结论2.

FJUT第三周寒假作业《第九集,离间计》栈用结构储存序列,下标,答案。value代表能力值,num代表数字

核心代码。

FJUT第三周寒假作业《第九集,离间计》栈