P2947 [USACO09MAR]Look Up S
题目传送门
暴力做法
暴力，可得58分。吸氧可得92分。（总之不能A）
#include
using namespace std;
int n;
int h[100005];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=1;i<=n;i++){
int dmax=0;
for(int j=i;j<=n;j++){
if(h[i] 正解——单调队列
其实寻找仰望对象时，可以使用单调队列进行维护。
由于满足 \(i \lt j\) 与 \(H_i \lt H_j\) 就是仰望对象，可以再循环内更新仰望对象。
时间复杂度是 \(O(n)\) 。
#include
using namespace std;
int n,h[100005],ans[100005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=n-1;i>=1;i--){
int j=i+1;
while(a[i]>=a[j]&&a[j]>0){
j=ans[j];
}
ans[i]=j;
}
for(int i=1;i<=n;i++){
cout< 没有O2最慢的点只有 \(62ms\)。真快！