首页 > 代码库 > 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 贪心 思维题 不错