myschool 相思树

题目描述

一群妖王排成一排站在苦情巨树下，寻找自己的转世恋人。
虽然都是妖王，但按照涂山的规定必须进行标号，标号为1的妖王排在最后面，标号为n的妖王排在最前面。每个妖王只有一个妖力值a[i]表示它们现在的地位。
妖王们是讲究实力的，当然不服比它妖力值低的居然可以排在前面，它们现在想知道在它前面，妖力值比它低，而且离它最远的距离是多少？

输入

输入n表示有n个妖王
第二行输入n个整数，表示每个妖王的妖力值a[i]

n<=2*10

1<=a[i]<=10

输出

对于每个妖王，妖力值比它低，而且离它最远的距离是多少，如果没有输出-1

样例输入

6

5 50 45 7 10 1

样例输出

4 3 2 1 0 -1

提示

对于第一个数:5,比它小的数字是1，1距离它最远，最远距离为4

对于第二个数:50,比它小的数字是45 7 10 1，1距离它最远，距离为3

对于第三个数:45,比它小的数字是7 10 1，1距离它最远，距离为2

对于第四个数:50,比它小的数字是10 1，1距离它最远，距离为1

对于第五个数:10,比它小的数字是1，1距离它最远，距离为0

对于第六个数:已经没有比它小的数字了，距离为-1

 #include <iostream>

 #include <stdio.h>

 using namespace std;

 int Min[], arr[];

 int main()

 {

     int n;

     while(scanf("%d",&n) != EOF)

     {

         for(int i = ; i < n; i++)

             scanf("%d",&arr[i]);

         Min[n-] = arr[n-];

         for(int i = n - ; i >= ; i--)

         {

             Min[i] = min(Min[i+], arr[i]);

         }

         for(int i = ; i < n;i++)

         {

             int l = i + ,r = n - ,mid;

             while(l <= r)

             {

                 mid = (l + r) / ;

                 if(Min[mid] < arr[i])

                     l = mid + ;

                 else r = mid - ;

             }

             printf("%d",l-i-);

             if(i<n-)

                 printf(" ");

         }

         printf("\n");

     }

     return ;

 }