首页 > 代码库 > POJ 3183:Stump Removal(模拟)
POJ 3183:Stump Removal(模拟)
http://poj.org/problem?id=3183
题意:有n个树桩,分别有一个高度h[i],要用Bomb把树桩都炸掉,如果炸的位置的两边树桩高度小于Bomb炸的树桩高度,那么小于树桩高度的两侧都是可以被炸掉的。而且有传递性。求把树桩全部炸掉要消耗的最少的Bomb数所炸的位置。
看样例: 1 2 5 4 3 3 6 6 2
炸位置3(即5)的话,那么2小于5,所以位置2被炸掉,因为1小于2,所以位置1被炸掉,因为4小于5,所以位于4被炸掉,因为3小于4,所以位置5被炸掉。因此丢一个Bomb到位置3就可以炸掉第1~5个树桩了。
思路:这道题因为看错OJ所以出现在RMQ专题里面。还想了一下RMQ怎么做...直接模拟就好了。(zhayao居然是违禁内容,只能用Bomb代替)
用一个flag判断当前序列是上升还是下降。如果是开始下降了,这个时候i-1就是顶峰,i-1这个位置肯定就是答案之一。还有等于的情况,如果之前的趋势是下降的,那么i-1并不会是答案,如果是上升的,那么i-1是答案,判完一次后把序列标记为上升。还有一个点在于,如果最后的序列是上升的,还要把n放入答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 #define N 50010 8 #define INF 0x3f3f3f3f 9 vector<int> vec;10 int h[N];11 12 int main() {13 int n;14 while(~scanf("%d", &n)) {15 for(int i = 1; i <= n; i++) scanf("%d", &h[i]);16 int ans = 0;17 vec.clear();18 int l = 1, tmp = h[1], flag = 1;19 for(int i = 2; i <= n; i++) {20 if(h[i] > tmp) { if(!flag) {flag = 1;} }21 else if(h[i] == tmp) { if(flag) vec.push_back(i-1); flag = 1; }22 else { if(flag) vec.push_back(i-1); flag = 0; }23 tmp = h[i];24 }25 if(flag) vec.push_back(n);26 for(int i = 0; i < vec.size(); i++) printf("%d\n", vec[i]);27 }28 return 0;29 }30 /*31 1332 133 234 1035 836 837 838 739 740 741 842 843 844 745 */
POJ 3183:Stump Removal(模拟)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。