codeforces 91B Queue

本文从WordPress迁移而来, 查看全部WordPress迁移文章

http://codeforces.com/problemset/problem/91/B

数据结构 单调栈 二分查找

题意:给一个序列,从右边开始看,对于第i个数字a[i],在右边找到一个比它小(严格小)的,最靠右的位置,k,输出k-i-1,如果一个都找不到,输出-1。对于序列的每个元素都要输出

维护一个单调栈,或者说维护一个单调的数组,这个栈是严格递减的,当前的a[i],如果比栈顶元素还小,那么可以直接入栈,并且由于是单调栈,所以一定无法在它前面找到一个元素比它自己要小,所以它对应的答案就是-1。如果当前元素比栈顶元素大,那么说明,一定可能可以在栈内找到一个元素比它小,由于栈是单调递减的,并且也是按顺序加入的,所以可以在栈内二分,找到比它小的而且最靠近栈底的元素。找到答案后,这个数字不能入栈,直接抛弃,否则会破坏栈的单调性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <stack>
using namespace std;
#define N 100010

struct elem{
int val,id;
elem(){}
elem(int _val,int _id){
val = _val; id = _id;
}
};
elem a[N];
int n,len,val[N],ans[N];

int binary(int key){
int low = 1 , high = len , res = -1;
while(low <= high){
int mid = (low + high) >> 1;
int _val = a[mid].val;
int _id = a[mid].id;
if(key > _val){
res = _id; high = mid - 1;
}
else low = mid + 1;
}
return res;
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n; i++)
scanf("%d",&val[i]);
a[1] = elem(val[n-1],n-1);
len = 1; ans[n-1] = -1;
for(int i = n-2; i >= 0; i--){
int _val = a[len].val;
if(val[i] < _val){
a[++len] = elem(val[i],i);
ans[i] = -1;
}
else
ans[i] = binary(val[i]);
}
for(int i = 0; i < n; i++)
printf("%d ",ans[i] == -1 ? -1 : ans[i]-i-1);
puts("");
}
return 0;
}