HZAU 1205 Sequence Number(双指针)
2024-08-24 02:46:25
题目链接:http://acm.hzau.edu.cn/problem.php?id=1205
【题意】给你一串数,要求你找到两个数a[i],a[j],使得a[i]<=a[j]且j>=i且j-i最大。
【分析】预处理1~i的最小值,然后从右往左双指针,维护右端点>左端点,如果右端点<1~L的最小值,则移动右端点。
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int N = 1e5+;
const double eps = 1e-;
int T,n,w[N],sum[N<<],p[N<<],cnt,m,ret[N];
int k,a[N],mi[N];
int main() {
while(~scanf("%d",&n)){ int ans=;
mi[]=1e9+;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
mi[i]=1e9+;
}
for(int i=;i<=n;i++){
mi[i]=min(mi[i-],a[i]);
}
for(int l=n,r=n;l>=;l--){
if(mi[l]>a[r]){
while(a[r]<mi[l]){
r--;
}
ans=max(ans,r-l);
}
else {
ans=max(ans,r-l);
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- java_jdk_JDK版本切换批处理脚本
- Intellij IDEA 的使用(创建项目、导入项目、同时部署多个项目、JRebel)等常见eclipse、myeclipse换idea必看
- Fast Intro To Java Programming (2)
- jeecms附件标签用法
- Java笔记(五)&hellip;&hellip;运算符
- Linux 内核开发—内核简单介绍
- codevs 4163 hzwer与逆序对
- 浅谈C#中的泛型
- 常见类——Object
- Python爬虫(二十)_动态爬取影评信息
- ScheduledThreadPoolExecutor Usage
- 以resnet作为前置网络的ssd目标提取检测
- python基础——列表
- Android ScrollView嵌套Recyclerview滑动卡顿,松手即停问题解决;
- springboot 读取 yml 配置的几种方式
- Nmap 7.70新增功能——扫描主机所有IP
- 测试char,varchar存储
- QT基础:QT 定时器学习
- mysql视图 新手的问答
- Oracle EBS客户化程序中格式化金额