940D Alena And The Heater
题目大意
给出两个长度为N的数组A,B,以及一种计算规律:
若t[i]=1,需满足t[i-1]=t[i-2]=t[i-3]=t[i-4]=0,以及max{A[i],A[i-1],A[i-2],A[i-3],A[i-4]} < l
若t[i]=0,需满足t[i-1]=t[i-2]=t[i-3]=t[i-4]=1,以及min{A[i],A[i-1],A[i-2],A[i-3],A[i-4]} > r
其他情况:t[i]=t[i-1](|l|,|r|≤109)
现在要使得运算一次的结果t=B,求满足条件的l,r(保证有解)
N≤100000
分析
由于l,r多解,所以我们不妨将l和r分别设为它们的极限-1e9和1e9,然后从B的第5为开始查找,由于数组可以向后传递,所以我们只需寻找与前一位相异的即可,找到后有两种情况:
1.t[i]=1,则l=max(l,max{A[i],A[i-1],A[i-2],A[i-3],A[i-4]}+1)
2.t[i]=0,则r=min(r,min{A[i],A[i-1],A[i-2],A[i-3],A[i-4]}-1)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int a[110000],b[110000];
char s[110000];
int main()
{ int n,m,i,j,k,le=-1e9,ri=1e9;
cin>>n;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%s",s+1);
for(i=1;i<=n;i++)
b[i]=s[i]-'0';
int be=0;
for(i=5;i<=n;i++)
if(b[i]!=be){
if(b[i]==1)
le=max(le,max(a[i]+1,max(a[i-1]+1,max(a[i-2]+1,max(a[i-3]+1,a[i-4]+1)))));
else
ri=min(ri,min(a[i]-1,min(a[i-1]-1,min(a[i-2]-1,min(a[i-3]-1,a[i-4]-1)))));
be=b[i];
}
cout<<le<<' '<<ri<<endl;
return 0;
}
最新文章
- PHP配置限制文件大小上传
- javascript中的队列结构
- Apache Spark探秘:三种分布式部署方式比较
- 如何将jsp中<;input>;设为只读
- MySQL的alter的使用
- ubuntu如何进入local、bin目录
- Evermoney -- 重新定义印象笔记编辑体验
- 【代码管理】GitHub超详细图文攻略 - Git客户端下载安装 GitHub提交修改源码工作流程 Git分支 标签 过滤 Git版本工作流
- 当view为wrap_conten时获取一个view的具体宽高
- 兼容ie8的前端下载方法
- Xilinx Vivado的使用详细介绍(1):创建工程、编写代码、行为仿真
- php,单引号与双引号的区别
- SQL SERVER 行列转换(动态)
- P3861 8月月赛A
- POJ 2242
- 巧用border特性实现聊天气泡效果
- 【Asp.net入门09】第一个ASP.NET 应用程序-处理窗体(1)
- nodejs环境使用jshint
- JavaScript事件的委派与事件的绑定
- C语言调用汇编