hihocoder 1797 单调递增子序列 二分

本文主要是介绍hihocoder 1797 单调递增子序列 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个包含N个整数的序列A1, A2, ... AN，你可以从中删除一段连续的子序列，使得剩下的序列是单调递增（不减）的。

请你求出最少删除几个元素。

Input

第一行包含一个整数N。  

第二行包含N个整数A1, A2, ... AN。  

对于30%的数据，1 ≤ N ≤ 1000  

对于100%的数据，1 ≤ N ≤ 100000, 1 ≤ Ai ≤ 1000000

Output

一个整数表示答案。

Sample Input

6  
1 2 3 1 1 5

Sample Output

2

 

题意简单明了，如果是连起来的话，肯定是前面的一段连续的还有后面的连续的

所以只需要在后面找到刚好大于等于前面的值，序列是有序的，直接二分查找，或者用lower_bound即可，

代码如下

 

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{int n;scanf("%d",&n);int l=0;int r=n-1;for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=1;i<n;i++){if(a[i]>=a[i-1])l++;elsebreak;}for(int i=n-1;i>=1;i--){if(a[i]>=a[i-1])r--;elsebreak;}//printf("%d   ",l);if(r==0||l==n-1){printf("0\n");return 0;}//printf("%d %d",l,r);int ans=r;for(int i=0;i<=l;i++){int p=int(lower_bound(a+r,a+n,a[i])-a);ans=min(ans,p-i-1);}printf("%d\n",ans);
}

 

这篇关于hihocoder 1797 单调递增子序列 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---