hdu5676 ztr loves lucky numbers DFS

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5676

题意：

定义幸运数为:只存在4和7且4和7数量相等的数，给出n，求比>=n的最小幸运数

思路：

因为n最多18位，幸运数最大是10个4，10个7，这种情况特判掉，爆longlong，其他的暴力搜出所有长度从2-18的幸运数，因为最多9个4,9个7，然后二分找出比这个数大的那个数

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 11000000;
17 
18 ll n,x[maxn],cnt;
19 
20 void dfs(int s4,int s7,int len,ll num){
21     if(s4==s7 && s4==len){
22         x[cnt++] = num;
23         return ;
24     }
25 
26     if(s4<len)
27         dfs(s4+1,s7,len,num*10+4);
28     if(s7<len)
29         dfs(s4,s7+1,len,num*10+7);
30 }
31 
32 int main(){
33     for(int i=1; i<=9; i++)
34         dfs(0,0,i,0);
35     int T = read();
36     while(T--){
37         cin >> n;
38         int pos = lower_bound(x,x+cnt,n)-x;
39         if(x[pos]) cout << x[pos] << endl;
40         else{
41             for(int i=0; i<10; i++) cout<<"4";
42             for(int i=0; i<10; i++) cout<<"7";
43             cout << endl;
44         }
45     }
46 
47     return 0;
48 }