贪心70pts求助
  • 板块P9147 签到题
  • 楼主rainygame
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/13 19:04
  • 上次更新2023/10/23 21:39:25
查看原帖
贪心70pts求助
804607
rainygame楼主2023/3/13 19:04

RT。

#include <bits/stdc++.h>
using namespace std;

int n, maxn, cnt = 1, l = 1, ans;
int a[1000001];

struct Section{
	int l, r, maxn, minn, len;
};
vector<Section> vec;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i=1; i<=n; i++){
		cin >> a[i];
		if (i == 1) continue;
		if (a[i] > a[i-1]){
			cnt++;
		}else{
			vec.push_back({l, i-1, a[i-1], a[l], cnt});
			maxn = max(maxn, cnt);
			l = i;
			cnt = 1;
		}
	}
	vec.push_back({l, n, a[n], a[l], cnt});
	maxn = max(maxn, cnt);
	
//	for (auto i: vec){
//		cout << i.l << ' ' << i.r << ' ' << i.maxn << ' ' << i.minn << ' ' << i.len << '\n';
//	}
	
	auto it = vec.begin(), it2 = vec.begin(), it3 = vec.begin();
	it3++;
	ans = maxn + (maxn != n);
	for (int i=1; i<=n; i++){
		if (it->r < i) it++;
		if (it2->r < (i-1)) it2++;
		if (it3->r < (i+1)) it3++;
		if (a[i+1]-a[i-1]>1 && (it != it2 || it2 != it3)){
			if (it == it2) ans = max(ans, it2->len+it3->len);
			else if (it == it3) ans = max(ans, it2->len+it3->len);
			else ans = max(ans, it2->len+it3->len+1);
		}
	}
	
	cout << ans;
	
	return 0;
}

主要思路就是分严格递增区间,然后枚举可以更改的,求hack。

2023/3/13 19:04
加载中...