Stump Removal
|
Time Limit: 1000MS |
Memory Limit: 65536K |
|
|
Total Submissions: 2459 |
Accepted: 1314 |
Description
Always thinking of
the cows' grazing experience, FJ has found that he must remove N (1 <= N
<= 50,000) unsightly stumps from the pasture. The stumps are conveniently
arranged in a straight line and numbered 1..N with each stump having some
height H_i (1 <= H_i <= 10,000).
FJ will use the traditional high explosives to destroy the stumps. These high
explosives are formulated to destroy adjacent stumps as long as those adjacent
stumps are strictly shorter than the nearest stump being destroyed. The blast
can continue past the closest adjacent stump to the next adjacent stump if it
is even shorter than the nearest stump just destroyed. As soon as a stump
encountered by the blast wave is not shorter, though, no more destruction
occurs on that side of the target stump (the other side follows the same rules
with whatever stumps might appear there).
Consider a line of nine stumps with these heights:
1 2 5 4 3 3 6 6 2
If FJ blows up the third stump (with height 5), then the second stump will also be destroyed (height 2) and the first stump (height 1) will also be destroyed. Likewise, the fourth stump (height 4) and fifth stump (height 3) will be destroyed since they are successively shorter, leaving the line like this:
* * * * * 3 6 6 2
Two more explosives (at stumps 7 and 8) will destroy the rest.
Help FJ determine the minimum number of explosive charges he needs to destroy
the stumps.
Input
Line 1: A single integer, N
Lines 2..N+1: Line i+1 contains H_i
Output
Lines 1..?: Each line contains one integer which is the index of a stump to blow up. The indices must be listed in increasing order.
Sample Input
9
1
2
5
4
3
3
6
6
2
Sample Output
3
7
8
Source
解题报告：其实这道题就是让我们求山顶的个数，扫描一遍就行找出即可，再注意边界问题！
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 50010;
int high[MAX];
int main()
{
int N, i;
scanf("%d", &N);
for (i = 1; i <= N; ++i)
{
scanf("%d", &high[i]);
}
if (high[1] >= high[2])//边界问题
{
printf("%d\n", 1);
}
for (i = 2; i <= N; ++i)
{
if (i == N)//边界问题
{
if (high[i] >= high[i - 1])
{
printf("%d\n", i);
}
}
else
{
if (high[i] >= high[i - 1] && high[i] >= high[i + 1])
{
printf("%d\n", i);
}
}
}
return 0;
}