博观而约取,厚积而薄发。这篇文章主要讲述#333 Div2 Problem B Approximating a Constant Range(尺取法)相关的知识,希望能为你提供帮助。
题目:http://codeforces.com/contest/602/problem/B
题意 :给出一个含有 n 个数的区间,要求找出一个最大的连续子区间使得这个子区间的最大值和最小值的差值不超过 1 ,最后输出这个子区间的长度。
分析:
因为区间里面的数只能相差1,我就用fs与fx来表示这个区间是上升区间还是下降区间
如果上升区间的话,遇到满足条件的也就是加进来区间的数与区间的开头a[st]相比较,如果是大1或者是相等就en++,直到不满足条件;
下降区间也是如此。。。
不满足条件的话st++。。同时还得重新判断区间的上升还是下降,因为经验不足,在这里卡了许久;
AC代码:
文章图片
文章图片
#include< stdio.h> #include< algorithm> using namespace std; int a[110000]; int main() { int n; scanf("%d",& n); for(int i=0 ; i< n ; i++) scanf("%d",& a[i]); int st=0,en=1; int fs=1,fx=1; ///标记fs是表示上升,fx表示下降 int maxx=-10; while(en< =n) {int t=a[st]; if(a[en]-t==1& & fs==1) { fx=0; en++; } else if(a[en]-t==-1& & fx==1) { fs=0; en++; } else if(a[en]-t==0) { en++; } else { int temp=en-st; maxx=max(maxx,temp); st++; int i=1; while(a[st]==a[st+i])///判断下一个区间是fs还是fx i++; if(a[st]-a[st+i]< 0) { fs=1; fx=0; } else { fs=0; fx=1; } } if(en==n) { int temp=en-st; maxx=max(maxx,temp); break; }} printf("%d\n",maxx); }
View Code【#333 Div2 Problem B Approximating a Constant Range(尺取法)】
推荐阅读
- permissions required by Vibrator.vibrate: android.permission.VIBRATE
- APP外包公司需要怎么甄别?
- 订阅号助手App发布 手机也能管理公众号了
- Android使用命令行操作数据库
- 移动4g上网伴侣怎样买?北京移动4g上网伴侣获得办法
- 小米新玩具是啥?小米新玩具或为小米路由器
- 小米路由器是啥?小米无线路由器技巧介绍
- 小米无线路由器啥时候上市?小米路由器上市时间介绍
- 小米无线路由器多少钱?小米路由器价格曝光