洛谷 P2947 [USACO09MAR]仰望Look Up
题目描述
Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once again standing in a row. Cow i has height H_i (1 <= H_i <= 1,000,000).
Each cow is looking to her left toward those with higher index numbers. We say that cow i 'looks up' to cow j if i < j and H_i < H_j. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.
Note: about 50% of the test data will have N <= 1,000.
约翰的N(1≤N≤10^5)头奶牛站成一排,奶牛i的身高是Hi(l≤Hi≤1,000,000).现在,每只奶牛都在向左看齐.对于奶牛i,如果奶牛j满足i<j且Hi<Hj,我们可以说奶牛i可以仰望奶牛j. 求出每只奶牛离她最近的仰望对象.
Input
输入输出格式
输入格式:
Line 1: A single integer: N
- Lines 2..N+1: Line i+1 contains the single integer: H_i
输出格式:
- Lines 1..N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.
输入输出样例
6
3
2
6
1
1
2
3
3
0
6
6
0
说明
FJ has six cows of heights 3, 2, 6, 1, 1, and 2.
Cows 1 and 2 both look up to cow 3; cows 4 and 5 both look up to cow 6; and cows 3 and 6 do not look up to any cow.
栈。
#include <cstdio>
#define N 100005
int a[N],num[N],ans[N],n,last,stack[N],top;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);num[i]=i;
if(!top) {stack[++top]=i;continue;}
else if(a[stack[top]]<a[i])
{
for(;(a[stack[top]]<a[i])&⊤top--)
ans[num[stack[top]]]=i;
}
stack[++top]=i;
}
for(int i=;i<=n;i++) printf("%d\n",ans[i]);
return ;
}
最新文章
- VS2015墙内创建ionic2 【利用nrm更换源,完美!】
- Maplace.js – 小巧实用的 jQuery 谷歌地图插件
- leetcode 179. Largest Number 求最大组合数 ---------- java
- .NET Core扩展IServiceCollection自动注册服务
- Android Layout XML属性
- 2.js基础
- css select 样式列表-----另一种样式列表
- 通过 CALayer 修改 UIImageView 的界面属性
- web.config配置详细说明
- iOS绘制view
- web开发 - 从零开始 - 02 - 常用标签
- 给节点设置tag【从零開始cocos3.0final 】
- 环信 之 iOS 客户端集成一:导入库
- 201521123062《Java程序设计》第5周学习总结
- Python logger 没打出行数
- python模块之sniffio
- Linux 使用tty0 显示10分钟自动关闭功能
- DHTMLX学习总结
- css3的overflow-anchor
- 爬虫进阶教程:极验(GEETEST)验证码破解教程