Stump Removal
| Time Limit: 1000MS | Memory Limit: 65536K |
| Total Submissions: 2379 | Accepted: 1282 |
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
USACO 2006 January Bronze
有N個草堆高度分别是Hi，現在要安裝炸藥，如果在某一個草堆高度為H0放炸藥，則兩邊比它矮的草堆（高度分别為H1,H2<H0）也會銷毀，同時，如果H1旁邊的草堆H3<H1,則H3草堆也會同時銷毀，之後的草堆也符合這種關系，比如： 1 2 5 4 3 3 6 6 2 第三個草堆點炸藥，則1<2<5>4>3==3<6==6>2. 是以在#3(5)點可以銷毀：#1~#5(1 2 5 4 3) 在#7(6)點可以銷毀：#6~#7(3 6) 在#8(6)點可以銷毀：#8~#9(6 2)，這樣就可以全部銷毀。
分析： 可以發現，點火的地方都是屬于草堆高峰的地方，要>=兩邊即可。
是以我們隻要将所有的資料存儲下來，然後找到巅峰處就可以輸出。 而我采用了一個線上判斷的方法，每次儲存三個last、now、next（目前次從鍵盤讀入的數）， 如果last<=now && now <= next，則輸出now的下标。 直到所有資料輸入完畢，再判斷最後一個數是否為草堆高峰：last<=now，如果成立，則輸出now的下标。
注意點： 1）如果三個數字連續如：3 3 3,要輸出中間那個數的下标。 2）注意末尾可能也是高峰的情況。 3）注意一開頭就是高峰的情況。
代碼（1AC）：
#include <cstdio>
#include <cstdlib>
#include <cstring>
int main(void){
int n;
int i, j;
int flag;
int now, last, next;
scanf("%d", &n);
last = -1, now = 0;
for (i = 1; i <= n; i++){
scanf("%d", &next);
if (last <= now && now >= next){
printf("%d\n", i - 1);
}
last = now;
now = next;
}
if (now >= last){
printf("%d\n", i - 1);
}
return 0;
}