当前位置:网站首页>Atcoder a mountaineer
Atcoder a mountaineer
2022-07-06 18:26:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB
Problem
Dave is a mountaineer. He is now climbing a range of mountains.
On this mountains, there are N huts located on a straight lining from east to west..
The huts are numbered sequentially from 1 to N. The west most hut is 1, the east most hut is N. The i-th hut is located at an elevation of hi meters.
Dave wants to know how many huts he can look down and see from each hut.
He can see the j-th hut from the i-th hut if all huts between the i-th hut and the j-th hut including the j-th one are located at equal or lower elevation than hi.
Note that the i-th hut itself is not included in the hut he can see from the i-th hut.
Input
The input will be given in the following format from the Standard Input.
N
h1
h2
:
hN
- On the first line, you will be given N(1≦N≦105), the number of huts.
- Then N lines follow, each of which contains hi(1≦hi≦105) the elevation of the i-th hut.
Achievements and Points
Your answer will be checked for two levels.
- When you pass every test case which satisfies 1≦N≦3,000, you will be awarded 30 points.
- In addition, if you pass all the rest test cases which satisfy 1≦N≦105, you will be awarded 70 more points, summed up to 100points.
Output
On the i-th line, output the number of huts Dave can see from the i-th hut. Make sure to insert a line break at the end of the output.
Input Example 1
3
1
2
3
Output Example 1
0
1
2
From each hut he can see every huts on the west.
Input Example 2
5
1
2
3
2
1
Output Example 2
0
1
4
1
0
From the 1st and 5th hut he can’t see any other huts.
From the 2nd hut he can only see the 1st hut.
From the 4th hut he can only see the 5th hut.
From the 3rd hut he can see every other huts.
Input Example 3
5
3
2
1
2
3
Output Example 3
4
2
0
2
4
Note that he can see the huts on the equal elevation.
Input Example 4
8
4
3
2
3
4
3
2
1
Output Example 4
7
2
0
2
7
2
1
0
Ideas : This is a simple question , But I have been facing big data TLE. Go straight up TLE Source code
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int num[] = new int[count];
int flag[] = new int[count];
for (int i = 0; i < count; i++) {
num[i] = sc.nextInt();
}
for (int i = 0; i < count; i++) {
for (int j = i - 1; j >= 0 && num[i] >= num[j]; j--,flag[i]++);
for (int j = i + 1; j < count && num[i] >= num[j]; j++,flag[i]++);
System.out.println(flag[i]);
}
}
}
Here are AC Source code . According to the above source code, it has been optimized to a certain extent . In a way , Changed some ideas , and https://oj.leetcode.com/problems/candy/ It's kind of like .
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = sc.nextInt(); int num[] = new int[count]; int[] back = new int[count]; int[] forward = new int[count]; for (int i = 0; i < count; i++) { num[i] = sc.nextInt(); } for (int i = 0; i < count; i++) { for (int j = i - 1; j >= 0 && num[i] >= num[j]; back[i] = back[i]+ back[j] + 1, j = j - back[j] - 1); } for (int i = count - 1; i >= 0; i--) { for (int j = i + 1; j < count && num[i] >= num[j]; forward[i] = forward[i]+ forward[j] + 1, j = j + forward[j] + 1); } for (int i = 0; i < count; i++) { System.out.println(back[i] + forward[i]); } }}
Copyright notice : This article is an original blog article . Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117392.html Link to the original text :https://javaforall.cn
边栏推荐
- Echart simple component packaging
- Grafana 9.0 is officially released! It's the strongest!
- 传输层 拥塞控制-慢开始和拥塞避免 快重传 快恢复
- 首先看K一个难看的数字
- Grafana 9.0 正式发布!堪称最强!
- 【中山大学】考研初试复试资料分享
- Four processes of program operation
- 2022 Summer Project Training (II)
- 文档编辑之markdown语法(typora)
- A method of sequentially loading Unity Resources
猜你喜欢
传输层 拥塞控制-慢开始和拥塞避免 快重传 快恢复
F200 - UAV equipped with domestic open source flight control system based on Model Design
UDP protocol: simple because of good nature, it is inevitable to encounter "city can play"
2019 Alibaba cluster dataset Usage Summary
Maixll-Dock 摄像头使用
Numerical analysis: least squares and ridge regression (pytoch Implementation)
队列的实现
面向程序员的精品开源字体
Blue Bridge Cup real question: one question with clear code, master three codes
TOP命令详解
随机推荐
C language college laboratory reservation registration system
Ms-tct: INRIA & SBU proposed a multi-scale time transformer for motion detection. The effect is SOTA! Open source! (CVPR2022)...
Will openeuler last long
Markdown syntax for document editing (typera)
Implementation of queue
[the 300th weekly match of leetcode]
Maixll dock camera usage
Transfer data to event object in wechat applet
Maixll-Dock 摄像头使用
文档编辑之markdown语法(typora)
30 minutes to understand PCA principal component analysis
echart简单组件封装
【LeetCode第 300 场周赛】
Codeforces Round #803 (Div. 2)
Insert dial file of Jerry's watch [chapter]
Introduction to the usage of model view delegate principal-agent mechanism in QT
44所高校入选!分布式智能计算项目名单公示
C语言自动预订飞机票问题
Echart simple component packaging
Virtual machine VirtualBox and vagrant installation