51Nod 1272 最大距离 (栈或贪心)
2024-09-07 14:03:54
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std; typedef long long ll;
struct node{int v, id;};
stack<node>q, sq; int main(){
int n;
scanf("%d", &n);
while(!sq.empty()) sq.pop();
int ans = ;
for(int i = ;i < n;i++){
int x;
scanf("%d", &x);
node a;
a.v = x; a.id = i;
if(sq.size() == || sq.top().v > x){
sq.push(a);
}
else{
while(sq.top().v <= x){
ans = max(ans, i - sq.top().id);
q.push(sq.top());
sq.pop();
if(sq.empty())
break;
}
while(!q.empty()){
sq.push(q.top());
q.pop();
}
}
}
printf("%d\n", ans);
return ;
}
后来提交一波的时候,最后一组数据超时,于是改用贪心,排序一遍过的:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = +;
struct node{
int id,v;
}a[maxn]; bool cmp(node xx,node yy)
{
if (xx.v!=yy.v)
return xx.v<yy.v;
return xx.id<yy.id;
} int main()
{
int n;
scanf("%d",&n);
for (int i=;i<n;i++)
{
scanf("%d", &a[i].v);
a[i].id=i;
}
sort(a,a+n,cmp);
int ans = ,Min=a[].id;
for (int i=;i<n;i++)
{
if (a[i].id > Min)
ans = max(ans, a[i].id-Min);
else Min = a[i].id;
}
printf("%d\n",ans);
return ;
}
最新文章
- wsdl中含ref=";s:schema";时处理的
- UVA5874 Social Holidaying 二分匹配
- android 项目学习随笔八(xUtils的BitmapUtils模块)
- python sklearn环境配置
- UESTC 2016 Summer Training #6 Div.2
- EC读书笔记系列之11:条款20、21
- Java8新特性-Lambda表达式
- nodejs server websocket
- style标签下的CSS代码的显示与实时编辑
- @Transactional导致无法动态数据源切换
- WAMP 默认mysql密码修改
- 恢复Ext3下被删除的文件
- IDEA无法启动debugger,报错Address localhost:1099 is already in use
- Java ftp上传文件方法效率对比
- 2017北京国庆刷题Day5 morning
- Selenium+Python常见定位方法
- 洛谷P3391文艺平衡树(Splay)
- 数据库SQL优化大总结之 百万级数据库优化方案 【转载】
- LOJ #6432. 「PKUSC2018」真实排名
- Memcached之缓存雪崩,缓存穿透,缓存预热,缓存算法