给定牛的高度和噪音值,牛只能听到比它低的牛的噪音,求最大的牛能够听到的噪音值。
我们维护一个单调递减栈,使用一个数组来记录第i只牛所能听到的噪音,最后求最大值即可
#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=50050;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int Case=1;
int a[N],ans1[N],ans2[N];
void solve(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(ans1,0,sizeof ans1);
memset(ans2,0,sizeof ans2);
stack<int> s;
for(int i=1;i<=n;i++){
while(!s.empty() && a[s.top()]<a[i]){
int t=s.top();s.pop();
if(!s.empty()) ans1[s.top()]=t;
}
s.push(i);
}
while(!s.empty()){
int t=s.top();s.pop();
if(!s.empty()) ans1[s.top()]=t;
}
for(int i=n;i>=1;i--){
while(!s.empty() && a[s.top()]<a[i]){
int t=s.top();s.pop();
if(!s.empty()) ans2[s.top()]=t;
}
s.push(i);
}
while(!s.empty()){
int t=s.top();s.pop();
if(!s.empty()) ans2[s.top()]=t;
}
printf("Case %d:\n",Case++);
for(int i=1;i<=n;i++){
printf("%d %d\n",ans2[i],ans1[i]);
}
}
int main(){
//IOS;
int t;cin>>t;
while(t--){
solve();
}
return 0;
}