喵哈哈村的排队

喵哈哈村的排队

发布时间: 2017年2月26日 16:13   最后更新: 2017年2月26日 16:14   时间限制: 1000ms   内存限制: 128M

描述

有一堆喵哈哈村的村民们在排队，他们从队列的尾部开始标号，标号为1的村民站在最后面，标号为n的村民站在队列的最前面，而且每个村民都拥有一个智商值a[i]。

这些村民有时候会觉得不开心，因为他们觉得凭什么一个智商比他低的人，可以站在他的前面！现在对于每个村民，他们都想知道，在他前面，智商比他低，离他最远的距离是多少。

输入

第一行n，表示有n只咸鱼
第二行n个整数，表示每个村民的智商值a[i].
n<=200000 1<=a[i]<=1000000000

输出

对于每个村民，输出智商比他的，且离他最远的距离是多少，如果没有输出-1

样例输入1 复制

6
10 8 5 3 50 45

样例输出1

2 1 0 -1 0 -1
注意注意，多组输入把我害惨了，今天就吸取教训了

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define N 200005
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
int n[N],k[N];
int m;
int BinarySearch(int begin,int end,int x){
    int mid,pos=0;
    int t=begin;
    if(begin==end)
        return -1;
    while(begin<end){
        mid=(begin+end)/2;
        if(k[mid]<x){
            begin=mid+1;
            pos=begin;
        }else {
            end=mid;
            pos=end;
        }
    }
    if(k[pos]==x&&k[pos-1]<x&&pos-1>=t)
        return pos-1;
    if(k[pos]==x)
        return -1;
    if(k[pos]<x)
        return pos;
    return pos-1;
}
int main(){
    while(~scanf("%d",&m)){
        mem(n);
        mem(k);
        for(int i=0;i<m;i++){
            scanf("%d",&n[i]);
        }
        k[m-1]=n[m-1];
        for(int i=m-2;i>=0;i--){
            k[i]=min(k[i+1],n[i]);
        }

        for(int i=0;i<m;i++){
            int ans=BinarySearch( i,m-1,n[i]);
            if(i)
                printf(" ");
            if(ans==-1)
                printf("-1");
            else
                printf("%d",ans-i-1);
        }
        printf("
");
    }

    return 0;
}