当前位置:网站首页>atcoder它A Mountaineer
atcoder它A Mountaineer
2022-07-06 10:19:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
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
思路:本题是个简单题,我却一直面对大数据时TLE。直接上TLE源代码
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]);
}
}
}
以下是AC源代码。依据上面的源代码做了一定程度上的优化。从某种程度上来说,更改了部分思路,和 https://oj.leetcode.com/problems/candy/有点像。
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]); } }}
版权声明:本文博客原创文章。博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117392.html原文链接:https://javaforall.cn
边栏推荐
- Declval (example of return value of guidance function)
- FMT open source self driving instrument | FMT middleware: a high real-time distributed log module Mlog
- Jielizhi obtains the currently used dial information [chapter]
- 《ASP.NET Core 6框架揭秘》样章发布[200页/5章]
- Heavy! Ant open source trusted privacy computing framework "argot", flexible assembly of mainstream technologies, developer friendly layered design
- Interview shock 62: what are the precautions for group by?
- FMT开源自驾仪 | FMT中间件:一种高实时的分布式日志模块Mlog
- OpenEuler 会长久吗
- Transfer data to event object in wechat applet
- D binding function
猜你喜欢
编译原理——自上而下分析与递归下降分析构造(笔记)
C语言指针*p++、*(p++)、*++p、*(++p)、(*p)++、++(*p)对比实例
Recommend easy-to-use backstage management scaffolding, everyone open source
std::true_type和std::false_type
Declval of template in generic programming
C语言通过指针交换两个数
微信为什么使用 SQLite 保存聊天记录?
Open source and safe "song of ice and fire"
编译原理——预测表C语言实现
简单易用的PDF转SVG程序
随机推荐
Heavy! Ant open source trusted privacy computing framework "argot", flexible assembly of mainstream technologies, developer friendly layered design
Introduction to the usage of model view delegate principal-agent mechanism in QT
《ASP.NET Core 6框架揭秘》样章发布[200页/5章]
Getting started with pytest ----- allow generate report
关于这次通信故障,我想多说几句…
Is it meaningful for 8-bit MCU to run RTOS?
Jerry's access to additional information on the dial [article]
2022暑期项目实训(三)
Scratch epidemic isolation and nucleic acid detection Analog Electronics Society graphical programming scratch grade examination level 3 true questions and answers analysis June 2022
Appium automated test scroll and drag_ and_ Drop slides according to element position
QT中Model-View-Delegate委托代理机制用法介绍
Interesting - questions about undefined
Top command details
Insert dial file of Jerry's watch [chapter]
TCP packet sticking problem
递归的方式
最新财报发布+天猫618双榜第一,耐克蓄力领跑下个50年
The difference between parallelism and concurrency
Excellent open source fonts for programmers
STM32 key state machine 2 - state simplification and long press function addition