经过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); } } } }