#333 Div2 Problem B Approximating a Constant Range(尺取法)
2024-09-02 05:07:48
题目: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[];
int main()
{
int n;
scanf("%d",&n);
for(int i= ; i<n ;i++)
scanf("%d",&a[i]);
int st=,en=;
int fs=,fx=;///标记fs是表示上升,fx表示下降
int maxx=-;
while(en<=n)
{ int t=a[st];
if(a[en]-t==&&fs==)
{
fx=;
en++;
}
else if(a[en]-t==-&&fx==)
{
fs=;
en++;
}
else if(a[en]-t==)
{
en++;
}
else
{
int temp=en-st;
maxx=max(maxx,temp); st++;
int i=;
while(a[st]==a[st+i])///判断下一个区间是fs还是fx
i++;
if(a[st]-a[st+i]<)
{
fs=;
fx=;
}
else
{
fs=;
fx=;
}
}
if(en==n)
{
int temp=en-st;
maxx=max(maxx,temp);
break;
} }
printf("%d\n",maxx);
}
最新文章
- Android多种进度条使用详解
- mysql安装innodb插件
- 商业智能BI和ERP的融合之路
- SCVMM配置
- Android-关于android:scrollbarStyle属性
- 自学Hadoop(一)
- MPAndroidChart
- Autofac 一个使用Demo
- 记微信开发(自定义回复&;关注回复)
- stsuts2的一些问题
- .Net Core 在Linux服务器下部署程序--(1). Windows 连接 Linux服务器
- 大数据学习之HDFS基本API操作(下)06
- jmeter实践之数据库参数传递
- charles最新破解jar文件,及浏览器证书安装
- http指定状态码
- Android自动化框架 模拟操作 模拟测试
- Mysql Insert Or Update语法实例
- 推荐一个入门最佳Git教程
- Python中i = i + 1与i + = 1的区别
- RK3288 手动设置电池电量
热门文章
- 第2章 构建springboot工程 2-2 使用Spring官方STS搭建SpringBoot工程
- PAT-l3-002堆栈
- 用于.NET环境的时间测试(转)
- rvm 安装后的补充工作:source $HOME/.profile
- 51NOD1835 完全图
- Django models模型ORM
- TinkerPop中的遍历:图的遍历策略
- 【IMOOC学习笔记】多种多样的App主界面Tab实现方法(一)
- jquery(&#39;tr&#39;,&#39;div&#39;)和jquery(&#39;tr,div&#39;)
- C# Socket 接受数据不全的处理