算法1
(暴力枚举) 模拟
题目怎么说就怎么写了,A和B可以用两个栈维护,我用的是数组模拟栈
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
void print() { cout << '\n'; }
template <typename T, typename...Args>
void print(T t, Args...args) { cout << t << ' '; print(args...); }
using P = pair<int, int>;
using ll = long long;
const int N = 200010;
// function
template <typename T> void chmax(T &x, T y) { x = max(x, y); }
template <typename T> void chmin(T &x, T y) { x = min(x, y); }
template <typename T = int>
vector<T> readVector(int n) {
vector<T> a(n);
for(T &x: a) cin >> x;
return a;
}
void solve(){
int n;
cin >> n;
n --;
int cnt = 0, Max = 0;
vector<int> A, B;
int x;
cin >> x;
A.pb(x);
while(n --) {
int x;
cin >> x;
if(x < A.back()) {
A.pb(x);
}
else {
if(B.empty() || x > B.back()) {
B.pb(x);
}
else {
chmax(Max, int(A.size()));
cnt ++;
A.clear();
while(B.size() && B.back() > x) {
A.pb(B.back());
B.pop_back();
}
A.pb(x);
}
}
}
cnt ++;
chmax(Max, int(A.size()));
if(B.size()) {
cnt ++;
chmax(Max, int(B.size()));
}
print(cnt, Max);
}
int main() {
ios
int t = 1; //cin >> t;
while(t --) solve();
return 0;
}