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

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 int Min[200005], arr[200005];
 5 int main()
 6 {
 7     int n;
 8     while(scanf("%d",&n) != EOF)
 9     {
10         for(int i = 0; i < n; i++)
11             scanf("%d",&arr[i]);
12         Min[n-1] = arr[n-1];
13         for(int i = n - 2; i >= 0; i--)
14         {
15             Min[i] = min(Min[i+1], arr[i]);
16         }
17         for(int i = 0; i < n;i++)
18         {
19             int l = i + 1,r = n - 1,mid;
20             while(l <= r)
21             {
22                 mid = (l + r) / 2;
23                 if(Min[mid] < arr[i])
24                     l = mid + 1;
25                 else r = mid - 1;
26             }
27             printf("%d",l-i-2);
28             if(i<n-1)
29                 printf(" ");
30         }
31         printf("
");
32     }
33     return 0;
34 }