Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.
One day Petya came across a positive integer n. Help him to find the least super lucky number which is not less than n.
The only line contains a positive integer n (1 ≤ n ≤ 10^100000). This number doesn't have leading zeroes.
Output the least super lucky number that is more than or equal to n.
4500
4747
47
47
题意：给你一个数字（位数<=10^100000）求不小于他且只由4,7并且4跟7的个数相等的最小的数字
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define MM(a,b) memset(a,b,sizeof(a));
char s[100000+10],s2[100000+10];
int main()
{
string s;
while(cin>>s)
{
int l=s.size();
if(l%2!=0||s>string(l/2,'7')+string(l/2,'4'))
{cout<<string(l/2+1,'4')<<string(l/2+1,'7')<<"\n";continue;}
int n4=l/2,n7=l/2;
int flag=0;
string ans;
for(int i=0;i<s.size();i++)
{
int ok=0;
if(n4>0)
{
if(flag||s[i]<'4') ok=1;
else if(s[i]=='4') for(int j=i+1;j<=l;j++)
{
if(j==l) {ok=1;break;}
char ch=j-i<=n7?'7':'4';
if(ch>s[j]) ok=1;
if(ch!=s[j]) break;
}
}
if(ok) {ans+="4";n4--;}
else {ans+="7";n7--;}
if(ans[i]>s[i]) flag=1;
}
cout<<ans<<"\n";
}
return 0;
}
分析：比赛时主要是比如4500<7744这样需要构造的数字没想出来。其实还是比较简单的，
因为要让数字足够小，所以从左往右贪心的尽可能的用4，如果当前数字<4，那么肯定就用4了，但是如果等于4呢，那就无法通过当前位判断出来了，需要假设当前位放4，那么为了>=数据4500，接下来的一个位数需要尽可能大，那么就用7，比如47，当到达第三位的时候7>0，说明当前位放4虽然跟数据的数值一样，但是是可以通过后面的数字构造出一个比数据大的，所以当前位放4，否则放7
注意string放元素是a+="w";