4721 排队
n 个小朋友排成一排,从左到右依次编号为 1∼n。
第 i 个小朋友的身高为 hi。
虽然队伍已经排好,但是小朋友们对此并不完全满意。
对于一个小朋友来说,如果存在其他小朋友身高比他更矮,却站在他右侧的情况,该小朋友就会感到不满。
每个小朋友的不满程度都可以量化计算,具体来说,对于第 i 个小朋友:
如果存在比他更矮且在他右侧的小朋友,那么他的不满值等于其中最靠右的那个小朋友与他之间的小朋友数量。
如果不存在比他更矮且在他右侧的小朋友,那么他的不满值为 −1。
请你计算并输出每个小朋友的不满值。
注意,第 1 个小朋友和第 2 个小朋友之间的小朋友数量为 0,第 1 个小朋友和第 4 个小朋友之间的小朋友数量为 2。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 h1,h2,…,hn。
输出格式
共一行,输出 n 个整数,第 i 个整数为第 i 个小朋友的不满值。
数据范围
前 5 个测试点满足 2≤n≤5。
所有测试点满足 2≤n≤105,1≤hi≤109。
输入样例1:
6
10 8 5 3 50 45
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100010;
int f[N], h[N];
int main ()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> h[i];
f[n + 1] = 2e9;
for(int i = n; i >= 1; i --) f[i] = min(f[i + 1], h[i]);
for(int i = 1; i <= n; i ++){
int l = i, r = n;
while(l < r){
int mid = l + r + 1 >> 1;
if(h[i] > f[mid]) l = mid;
else r = mid - 1;
}
printf("%d ", r - i - 1);
}
return 0;
}
//树状数组 + 离散化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
vector<int> alls;
int w[N];
int n;
int ans[N];
int tr[N];
int find(int x){
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
void update(int x, int c){
for(int i = x; i <= alls.size(); i += i & -i) tr[i] = max(tr[i], c);
}
int query(int x){
int mx= 0;
for(int i = x; i >= 1; i -= i & -i) mx = max(tr[i], mx);
return mx;
}
int main (){
cin >> n;
for(int i = 1; i <= n; i ++){
scanf("%d", &w[i]);
alls.push_back(w[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for(int i = n; i >= 1; i --){
int x = find(w[i]);
update(x, i);
x = query(x - 1);
if(x < i) ans[i] = -1;
else ans[i] = x - i - 1;
}
for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';
return 0;
}
//stack
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int w[N];
int n;
int stk[N];
int ans[N];
int main (){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> w[i];
int top = 0;
for(int i = n; i >= 1; i --){
if(!top || w[i] <= w[stk[top]]) ans[i] = -1;
else{
int l = 1, r = top;
while(l < r){
int mid = l + r >> 1;
if(w[stk[mid]] < w[i]) r = mid;
else l = mid + 1;
}
ans[i] = stk[l] - i - 1;
}
if(!top || w[i] < w[stk[top]]) stk[++top] = i;
}
for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';
return 0;
}