CF 1272 D. Remove One Element
2 seconds
256 megabytes
standard input
standard output
You are given an array aa consisting of nn integers.
You can remove at most one element from this array. Thus, the final length of the array is n−1n−1 or nn.
Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.
Recall that the contiguous subarray aa with indices from ll to rr is a[l…r]=al,al+1,…,ara[l…r]=al,al+1,…,ar. The subarray a[l…r]a[l…r] is called strictly increasing if al<al+1<⋯<aral<al+1<⋯<ar.
The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of elements in aa.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the ii-th element of aa.
Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array aa after removing at most one element.
5
1 2 5 3 4
4
2
1 2
2
7
6 5 4 3 2 4 3
2
In the first example, you can delete a3=5a3=5. Then the resulting array will be equal to [1,2,3,4][1,2,3,4] and the length of its largest increasing subarray will be equal to 44.
这个题我自己的写法WA了,改来改去太复杂,所以后来直接借用学长的思路。
用学长的思路写这篇博客吧,学长原贴:https://www.cnblogs.com/xyq0220/p/12036109.html
O(n) 预处理出l[i]为i作为终点的最长严格递增子段,r[i]为i作为起始点的最长严格递增子段。 不删除一个元素,ans=max{l[i]},(1<=i<=n)。
删除一个元素,ans=max{l[i−1]+r[i+1]},(1<i<n&&a[i−1]<a[i+1])
1 #include<bits/stdc++.h>
2 #define fi first
3 #define se second
4 #define lson l,mid,p<<1
5 #define rson mid+1,r,p<<1|1
6 #define pb push_back
7 #define ll long long
8 using namespace std;
9 const int inf=1e9;
10 const int mod=1e9+7;
11 const int maxn=2e5+10;
12 int n;
13 int a[maxn];
14 int l[maxn],r[maxn];
15 int main(){
16 ios::sync_with_stdio(false);
17 //freopen("in","r",stdin);
18 cin>>n;
19 int ans=0;
20 for(int i=1;i<=n;i++){
21 cin>>a[i];
22 if(a[i]>a[i-1]) l[i]=l[i-1]+1;
23 else l[i]=1;
24 ans=max(ans,l[i]);
25 }
26 r[n]=1;
27 for(int i=n-1;i>=1;i--){
28 if(a[i]<a[i+1]) r[i]=r[i+1]+1;
29 else r[i]=1;
30 }
31 for(int i=2;i<n;i++){
32 if(a[i+1]>a[i-1]) ans=max(ans,l[i-1]+r[i+1]);
33 }
34 cout<<ans<<endl;
35 return 0;
36 }
类似于B 的隔板法,将遍历过程中不符合严格单调递增的作为板子,进行分割。
但是分割之后,隔间与隔间是相互联系的,与走楼梯的经典迭代问题相似。
这题关键就在于怎么巧妙运用隔板法和迭代编写程序。
这题虽然很简单,但是改了好几次,没办法,菜是原罪。
最新文章
- win8.1 Framework3.5安装不上的问题
- mysql中常用的控制流函数
- highcharts 不显示X轴 Y轴 刻度
- 免费下载:320+ 手绘风格 Apple iOS7 图标
- 使用getGenericSuperclass()和getActualTypeArguments()将DAO做成泛型
- php代码结尾不要添加结尾标记
- HDD-FAT32 ZIP-FAT32
- linux下监控进程需掌握的四个命令
- alpha冲刺第四天
- Python 学习开篇
- svg(可缩放矢量图形)
- ogg 12.3 for sqlserver 2016/2014 CDC模式配置
- Triangle Count
- 【Selenium】【BugList5】chrom窗口未关闭,又新开窗口,报错:[8564:8632:0522/111825.341:ERROR:persistent_memory_allocator.cc(845)] Corruption detected in shared-memory segment.
- java性能分析工具
- 10.11 rbac权限
- Linux系统运维笔记(一),查看系统版本和设置系统时间
- 高并发第六弹:线程封闭(ThreadLocal)
- HighCharts画时间趋势图,标示区以及点击事件操作
- Parencodings(模拟)