Vijos P1062 迎春舞会之交谊舞

题目链接:https://vijos.org/p/1062

题意:输入n(n <= 1500)个女生左边有多少个男生。每个女生都和她左边最近的男生跳舞。

输出每个女生到可以与之跳舞的男生之间有几个男生;(包括跳舞的男生)

input

6
4 5 6 6 6 6
output

1 1 1 4 5 6

思路:简单的递推即可；并没有用到栈。。对于第i个女生，易知当该女生左边男生的数量比前一个女生的数量多时，结果就是1.但是当出现连续的相等时，即表示这些女生之前没有男生，这时我们就需要先前找"可用"的男生了。即向前一个位置，就有一个最近的男生被前一个位置的女生抢走了。这是代表当前的第i位的女生可选的男生数量-1了。一直到可选的数量比当前比较的女生数量多时，她就可以从中取一个了；其实就是模拟；时间复杂度为O(n^2)的

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define inf 0x7fffffff

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

const int N = ;

int f[N];

int main()

{

    int n;

    read1(n);

    rep1(i,,n) read1(f[i]);

    printf("");

    rep1(i,,n){

        int cnt = ,tmp = f[i];

        for(int j = i - ;tmp <= f[j];j--)

            tmp--,cnt++;

        printf(" %d",cnt+);

    }

    puts("");

    return ;

}