题解里没有的思路但WA45pts
查看原帖
题解里没有的思路但WA45pts
1473266
Andy0121楼主2024/11/27 22:01
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	int cnt = 1;
	cin >> n;
	int a[n];
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}
	int maxn[n];
	memset(maxn,0,sizeof(maxn));
	maxn[n-1] = a[n-1];
	for(int i = n-2;i >= 0;i--){
		maxn[i] = max(maxn[i+1],a[i]);
	}//"后缀最大"(?) 
	int l = a[0],maxx = a[0],i = 1;
	while(i < n){
		if(a[i] < l){
			cnt++;
			l = a[i];
			maxx = a[i];
			i++;
			continue;
		}//如果小于左端点就另开一个 
		if(a[i] >= maxx){
			maxx = a[i];
			i++;
			continue;
		}//如果不小于当前最大值就加进来 
		if(maxn[i] >= maxx){
			maxx = max(maxx,a[i]);
			i++;//如果右边还有可以作为右端点的(大于等于当前最大值)就加上他 
		}else{
			cnt++;
			l = a[i];
			maxx = a[i];
			i++;
		}//如果右边都比他小就再开一个 
	}
	cout << cnt;
	return 0;
} 
2024/11/27 22:01
加载中...