Skip to content

14214: 【原4214】送钱活动

题目

题目描述

author: 泰玛什 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4214

Background

世界上有一个被称之为ETS的神秘组织,每周信徒们都会参加ETS组织的集会活动,向组织送钱以表示自己的忠诚。

Description

在集会报道的过程中,n个信徒按编号排成一列按顺序签到,其中第1号信徒在队尾,而第n号信徒在队首。其中,第i号信徒的信仰值为\(a_i\)。

对第i号信徒而言,若存在一个j号信徒排在他的前面并且信仰值比他小,他就会感到不开心。第i号信徒的不开心值由最靠队伍前部的满足条件的j决定,且其不开心值为\(j-i-1\)。若不存在满足条件的j,则不开心值为-1。

你现在的任务是算出每个信徒的不开心值。

Input Format

第一行有一个整数\(n\),表示信徒的人数。

接下来一行,一共\(n\),第i个数表示第i号信徒的信仰值\(a_i\)。

Output Format

输出共一行,n个数表示第i号信徒的不开心值。

Sample Input

6
10 8 5 3 50 45

Sample Output

2 1 0 -1 0 -1

Limit

  • 对于40%的数据,\(n \leq 1000, 1 \leq a_i \leq 1000\)

  • 对于100%的数据,\(n \leq 10^5, 1 \leq a_i \leq 10^9 \)

zqy2018's solution

/*
    Hint: use monotonic stack
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
pair<int, int> pp[100005];
int n, a[100005], ans[100005] = {0}, pos[100005];
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read(), pp[i].first = a[i], pp[i].second = i;
    sort(pp + 1, pp + n + 1);
    for (int i = 1; i <= n; ++i)
        pos[pp[i].second] = i;
}
void solve(){
    int cur = n;
    for (int i = n; i >= 1; --i){
        while(cur >= 1 && pp[cur].first > a[i]){
            if(pp[cur].second < i)
                ans[pp[cur].second] = i;
            cur--;
        }
        if(cur < 1) break;
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i] ? ans[i] - i - 1: -1);
}
int main(){
    init();
    solve();
    return 0;
}