首页 > 代码库 > hdu 4550 贪心 思维题 不错
hdu 4550 贪心 思维题 不错
http://acm.hdu.edu.cn/showproblem.php?pid=4550
想了挺久,然后各种分类 终于AC,如果是现场,对自己没信心的话,估计还是要WA,,,,,,然后搜题解,发现人家都认为是简单题,看来我还是太弱了,牡丹江没有做出来K看来还是自己贪心和思维有问题
d是一个Deque
最朴素的算法是,如果当前的数<=d.front(),那么插入队列的前面,否则插入队列后面,但是有零所以需要单独处理,还是自己多举例找规律
我的策略:
1、记录0的个数zero,最小非零的数的个数cnt
2、判断的策略见代码
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <deque>#include <vector>#include <queue>using namespace std;#define IN(s) freopen(s,"r",stdin)const int MAXN = 100+5;char s[MAXN];int a[MAXN],len;void solve(){ deque<int>d; int _min=1000,zero=0,cnt=0; for(int i=0;i<len;i++) if(a[i]) _min=min(_min,a[i]); else zero++; for(int i=0;i<len;i++) if(a[i] == _min) cnt++; d.push_front(a[0]);// if(a[0] == _min)cnt--; if(a[0] == 0)zero--; for(int i=1;i<len;i++) { if(a[i]){ if(d.front()) { if(a[i]==_min)cnt--; if(a[i]<=d.front())d.push_front(a[i]); else d.push_back(a[i]); } else//首位是0 { if(cnt==1 && a[i]==_min) { cnt--; d.push_front(a[i]); continue; } //后面不止一个最小数 if(a[i]==_min)cnt--; d.push_back(a[i]); } continue; } //a[i]是0的情况 zero--; if(cnt)//后面还有最小值 d.push_front(a[i]); else d.push_back(a[i]); } for(int i=0;i<d.size();i++) printf("%d",d[i]); putchar('\n');}int main(){ //IN("hdu4550.txt"); int ncase; scanf("%d",&ncase); while(ncase--) { scanf("%s",s); len=strlen(s); for(int i=0;i<len;i++) a[i]=s[i]-'0'; solve(); } return 0;}
hdu 4550 贪心 思维题 不错
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。