2016 Personal Training #8 Div.2 I - Lucky Numbers CodeForces 95B

时间:2021-01-16 04:27:28

CodeForces 95B

经过11遍的WA和TLE终于迈向胜利T_T,题不难但是要考虑很多细节,这种题也是接触太少以前都是嫌麻烦就放弃了,所以借这题也是有不少收获,在此告诫千万别放弃坚持就是胜利!

题意:幸运数是只由4和7组成,超级幸运数是这个幸运数的4和7一样多,给你一个数求最小但比给的数大的超级幸运数,我就只提供几组样例供大家参考测试吧:

a.74777477 b.678678 c.456456 d.567567 e.74477477 f.744747。可能超时的自行解决。

代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
char str[100005];
int flag[100005];
void print(int len)
{
  for(int i=0;i<len/2;i++)
  {
    printf("4");
  }
  for(int j=len/2;j<len;j++)
  {
    printf("7");
  }
  printf("\n");
}
int main()
{
  scanf("%s",str);
  int len=strlen(str);
  memset(flag,0,sizeof(flag));
  if(len%2)
  {
    print(len+1);
  }
  else
  {
    if((str[0]-'0')>7)
    {
      print(len+2);
    }
    else
    {
      int cnt=0,x=0,y=0;
      for(int i=len-1;i>=0;i--)
      {
        if((str[i]-'0'+cnt)>7)
        {
          if(i==0)
          {
            print(len+2);return 0;
          }
          cnt=1;str[i]='4';
        }
        else if((str[i]-'0'+cnt)>4&&(str[i]-'0'+cnt)<7)
        {
          cnt=0;str[i]='7';
          flag[i+1]=1;
        }
        else if((str[i]-'0'+cnt)<4)
        {
          cnt=0;str[i]='4';
          flag[i+1]=1;
        }
        else if((str[i]-'0'+cnt)==4)
        {
          str[i]='4';
          if(cnt)
          {
            flag[i+1]=1;
          }
          cnt=0;
        }
        else
        {
          str[i]='7';
          if(cnt)
          {
            flag[i+1]=1;
          }
          cnt=0;
        }
      }
      int pos=-1;//printf("#%s\n",str);
      for(int i=0;i<len;i++)
      {
        if(flag[i])
        {
          pos=i;break;
        }
      }
      if(pos!=-1)
      for(int i=pos;i<len;i++)
      {
        str[i]='4';
      }
      for(int i=0;i<len;i++)
      {
        if(str[i]=='4') x++;
        else y++;
      }
      if(x==y) printf("%s\n",str);
      else if(x>y)
      {
        int ans=x-y,flag=0;
        for(int i=len-1;i>=0;i--)
        {
          if(ans==0)
          {
            printf("%s\n",str);//flag=1;
            break;
          }
          else
          {
            if(str[i]=='4')
            {
              str[i]='7';ans-=2;
            }
          }
        }
        //if(flag==0) print(len+2);
      }
      else
      {
        int ans=y-x;//printf("#%d\n",ans);
        for(int i=len-1;i>=0;i--)
        {
          int p=0;
          if((str[i]-'0')==4)
          {
            for(int j=0;j<i;j++)
            {
              if(str[j]=='4') p++;
            }
            if(((len-1-i)+p)>=len/2)
            {
              str[i]='7';//printf("@%d\n",len-i);
              ans+=2;
              for(int j=i+1;j<len;j++)
              {
                if(ans==0)
                {
                  printf("%s\n",str);return 0;
                }
                if(str[j]=='7')
                {
                  str[j]='4';ans-=2;
                }
              }
              printf("%s\n",str);return 0;
            }
          }
        }
        print(len+2);
      }
    }
  }
}