返回信息流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 100 points.
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
下面是我的解法：
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
int main(void)
{
long int n,l,r,cnt;
string number;
cin>>n;
std::getline(cin,number);
int steps[n];
long int res[n][2];
for(long int i=0;i<n;i++)
{
std::getline(std::cin, number);
steps[i]=atoi(number.c_str());
res[i][0]=i;
res[i][1]=0;
}
for(long int i=0;i<n;i++)
{
cnt=res[i][1];
for(l=res[i][0]-1;l>=0;l--)
{
if(steps[l]<=steps[i])
cnt++;
else
{
break;
}
}
//cout<<cnt<<endl;
for(r=i+1;r<n;r++)
{
if(steps[r]<steps[i])
cnt++;
else if(steps[r]==steps[i])
{
cnt++;
if(res[r][1]<cnt)
{
res[r][0]=l+1;
res[r][1]=cnt;
}
}
else
{
if(res[r][1]<cnt+1)
{
res[r][0]=l+1;
res[r][1]=cnt+1;
}
break;
}
}
cout<<cnt<<endl;
}
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / cpp / #83828同步于 2014/11/2
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
帮忙看哈这个怎么优化，就只剩最后一个是TLE了
nullne
2014/11/2镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
时间复杂度O(n)。试试看：
#!/usr/bin/env python3
def right_sees(heights):
stack = []
sees = [0 for x in heights]
for i,h in enumerate(heights):
while len(stack)>0:
oi, oh = stack[-1]
if oh < h:
sees[oi] = i - oi - 1
stack.pop()
else:
break
stack.append((i,h))
lh = len(heights)
for oi, oh in stack:
sees[oi] = lh - oi - 1
return sees
def left_sees(heights):
return list(reversed(right_sees(list(reversed(heights)))))
def two_side_sees(heights):
l = left_sees(heights)
r = right_sees(heights)
a = [ls+rs for (ls,rs) in zip(l,r)]
# print("DEBUG: input {} l {} r {} a {}".format(heights,l,r,a))
return a
examples = [
([1,2,3], [0,1,2]),
([1,2,3,2,1], [0,1,4,1,0]),
]
def run_examples():
for inp,outp in examples:
result = two_side_sees(inp)
if result == outp:
print("PASS: input {}, output {}".format(inp, result))
else:
print("ERROR: input {}, expected {}, actual {}".format(inp,outp,result))
run_examples()
先谢一个再慢慢看
【 在 nuanyangyang 的大作中提到: 】
: 时间复杂度O(n)。试试看：
: [code=python]
: #!/usr/bin/env python3
: ...................
首先你让别人看你代码请最起码注释变量用途。这个题应该是线性的，即从每个点向左右两边扩展，找比这个点小的（有点像判断回文），这个题应该是有动态规划性质的，比如，Input Example 4
8
4
3
2
3
4
3
2
1
对于第四个数字3来说，它记录了前两个比他低的，即3,2，第五个数字4比第四个数字3大，那么，3,2就可以不判断了，直接去判断第一个数字4，应该能缩短不少时间。
我没看你代码，要是跟你想的一样就请忽略吧[ema3]
是应该加注释的
思路基本一样的
【 在 ajin 的大作中提到: 】
: 首先你让别人看你代码请最起码注释变量用途。这个题应该是线性的，即从每个点向左右两边扩展，找比这个点小的（有点像判断回文），这个题应该是有动态规划性质的，比如，Input Example 4
: 8
: 4
: ...................
定义一个栈，先从左往右扫描，每个元素比栈顶对应高度小就把下标入栈，否则就向外弹到满足条件。入栈的同时可以判断向左看多远，完事反过来再来一次加起来就行了。暖神的代码应该也是这个思路吧
通过『我邮2.0』发布
恩 昨天好好研究了一下暖神的代码 渣渣看了很久
【 在 glazard 的大作中提到: 】
: 定义一个栈，先从左往右扫描，每个元素比栈顶对应高度小就把下标入栈，否则就向外弹到满足条件。入栈的同时可以判断向左看多远，完事反过来再来一次加起来就行了。暖神的代码应该也是这个思路吧
: 通过『我邮2.0』发布