浙江财经大学
信息管理与工程学院

Codeforces 90 D/91 B. Queue

本文由 Ocrosoft 于 2016-10-21 10:48:43 发表

There are n walruses standing in a queue in an airport. They are numbered starting from the queue’s tail: the 1-st walrus stands at the end of the queue and the n-th walrus stands at the beginning of the queue. The i-th walrus has the age equal to ai.

The i-th walrus becomes displeased if there’s a younger walrus standing in front of him, that is, if exists such j (i < j), that ai > aj. Thedispleasure of the i-th walrus is equal to the number of walruses between him and the furthest walrus ahead of him, which is younger than the i-th one. That is, the further that young walrus stands from him, the stronger the displeasure is.

The airport manager asked you to count for each of n walruses in the queue his displeasure.

Input

The first line contains an integer n (2 ≤ n ≤ 105) — the number of walruses in the queue. The second line contains integers ai(1 ≤ ai ≤ 109).

Note that some walruses can have the same age but for the displeasure to emerge the walrus that is closer to the head of the queue needs to be strictly younger than the other one.

Output

Print n numbers: if the i-th walrus is pleased with everything, print “-1” (without the quotes). Otherwise, print the i-th walrus’s displeasure: the number of other walruses that stand between him and the furthest from him younger walrus.

Examples
input
6
10 8 5 3 50 45

output
2 1 0 -1 0 -1 

input
7
10 4 6 3 2 8 15

output
4 2 1 0 -1 -1 -1 

input
5
10 3 1 10 11

output
1 0 -1 -1 -1 

Solution

题意:给出一个数字序列,对于每个i位置的数字,找到比它小的且最右边的数字,其位置为j,对于这个i位置的数字,输出i-j-1;如果找不到这样的j位置的数字,输出-1。
其实就是问每个数字跟他右边的最小的数字间隔了几个数(不包含两边)。
思路:好像是个DP题,也可以模拟去做。当然暴力模拟稍微简单点。
单纯的暴力就是两个for循环,肯定超时的。所以先对数字大小进行排序,这样省去一个for循环,然后再对索引位置进行循环就好了。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 100000 + 10;
const int MOD = 100000;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
vector<pair<int,int> > v;
int ans[MAXN]={0};
int main()
{
	int n;cin>>n;
	for(int i=0;i<n;i++)
	{
		int t;cin>>t;
		v.push_back(make_pair(t,i));
	}
	sort(v.begin(),v.end());
	int t=0;
	for(int i=0;i<n;i++)
	{
		t=max(v[i].second,t);
		ans[v[i].second]=t-v[i].second-1;
	}
	for(int i=0;i<n;i++)
		printf("%d ",ans[i]);
	return 0;
}

欢迎分享与转载,请保留链接与出处。Ocrosoft » Codeforces 90 D/91 B. Queue

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址