首页 > 代码库 > hdu 4105 贪心思想
hdu 4105 贪心思想
淋漓尽致的贪心思想
波谷一定是一位数,波峰一位数不够大的时候添加到两位数就一定够大了的。
当在寻找波谷碰到零了就自然当成波谷。
当在寻找波峰时碰到零时,将前面的波谷加到前一个波峰上,让当前的零做波谷,使得波谷的值尽量小,这就是本题最关键的贪心思想,一直想不到。
代码中:a表示前一个值,b表示当前考虑的值,tag为偶数时表示正在寻找波谷,奇数时在寻找波峰。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<map> using namespace std; char data[5999]; int main() { int n, m, k; while(scanf("%d", &n) != EOF) { scanf("%s", data); //cout<<data<<endl; int a, b, tag = 0; a = 11; b = 0; int ans = 0; for(int i = 0; i < n; i ++) { b = (data[i] - '0'); if(tag % 2 == 0){ if(b < a){ a = b; } else { i ++; a = data[i]-'0'; } } else { if(b > a) { a = b; } else { if(b == 0) { while(data[i] == '0'){ i ++; if(i >= n) break; } //贪心思想,有0就一定让他做波谷,把原先的波谷a给到他的前一个波峰上 a = 0; //0做波谷 b = data[i]-'0'; a = b; } else { i ++; a = b*10 + (data[i] - '0'); } } } if(i >= n) break; ans ++; tag ++; } printf("%d\n", ans-1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。