本文共 1586 字，大约阅读时间需要 5 分钟。
其实不太理解为什么10超时了。。
这题似乎是有贪心优化的方法的，我下面直接暴力了。。
暴力之余要特判两个点：1.超时点就是n=10的时候，直接算一下247
2.WA点就是如果有两个数，且一个为0，那样不算先导零，结果按我的代码也是要特判的。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define lson l, m, rt<<111 #define rson m+1, r, rt<<1|112 #define INF 0x3f3f3f3f13 typedef unsigned long long ll;14 using namespace std;15 char s[110];16 int a[110], vis[110], sum1, sum2, mini, n;17 void dfs(int cur)18 {19 if(cur < n/2){20 for(int i = 0; i < n; i++){21 if(cur == 0&&a[i] == 0) continue;//排除先导零 22 if(!vis[i]){23 vis[i] = 1;24 sum1 = sum1*10+a[i];25 cur++;26 dfs(cur);27 sum1 = (sum1-a[i])/10;28 cur--;29 vis[i] = 0;30 }31 } 32 }33 else if(cur == n){34 mini = min(abs(sum2-sum1), mini);35 }36 else{37 for(int i = 0; i < n; i++){38 if(cur == n/2&&a[i] == 0) continue;//排除先导零 39 if(!vis[i]){40 vis[i] = 1;41 sum2 = sum2*10+a[i];42 cur++;43 dfs(cur);44 sum2 = (sum2-a[i])/10;45 cur--;46 vis[i] = 0;47 }48 } 49 }50 51 }52 int main()53 {54 int t;55 scanf("%d", &t);56 char c = getchar(); 57 while(t--){58 gets(s); 59 int len = strlen(s);60 n=0, sum1 = 0, sum2 = 0, mini = INF;61 for(int i = 0; i < len; i++){62 a[n++] = s[i++]-'0';63 }64 if(n == 10){ //不特判就超时，只有这一条超时 65 printf("247\n"); 66 continue;67 }68 else if(n == 2&&(a[0]==0||a[1]==0)){ //如果只有两位，且有一位为0也要特判 69 printf("%d\n", max(a[0], a[1]));70 continue;71 } 72 dfs(0);73 printf("%d\n", mini);74 } 75 }
转载于:https://www.cnblogs.com/Surprisezang/p/9019669.html