60pt求助
查看原帖
60pt求助
326254
LonginusMonkey楼主2022/8/30 23:43
#include<bits/stdc++.h>
using namespace std;
vector<int> vec;
int top;
int arr[100100];
int pre[100100];
int pre2[100010];
int to[100100];
int main() {
	int n;
	cin >> n;
	vec.resize(n+10);
	for(int i=1; i<=n; ++i) {
		cin >> arr[i];
	}
	for(int i=1; i<=n; ++i) {
		while(top!=0 && arr[vec[top]] < arr[i]) {
			top--;
		}
		pre[i] = vec[top];
		vec[++top] = i;
	}
	vec.empty(); top = 0;
	vec.resize(n+10);
	for(int i=1; i<=n; ++i) {
		int u = 1;
		while(top!=0 && arr[vec[top]] >= arr[i]) {
			top--;
		}
		if(top == 0) {
			pre2[i] = 0;
		}
		else pre2[i] = vec[1];
		vec[++top] = i;
	}
	int ans = 0;
//	for(int i=1; i<=n; ++i) {
//		cout << pre[i] << " ";
//	}
//	cout << endl;
//	for(int i=1; i<=n; ++i) {
//		cout << pre2[i] << " ";
//	}
//	cout << endl;
	for(int i=1; i<=n; ++i) {
		for(int j=pre[i]+1; j<=i; ++j) {
			if(arr[j] < arr[pre2[i]] || pre2[i] == j || pre2[i] == 0) {
				ans = max(ans, i-j+1);
				break;
			}
		}
	}
	cout << ans;
	return 0;
}
2022/8/30 23:43
加载中...