就是给你一个数,排列组合,然后问如何排列之间的差值最小。
我之前的想法是一个递归,然后两个for循环枚举L1和L2,结果TLE了,然后想了一下剪枝发现没办法剪,然后看了一下别人的代码,用了next_permutation函数,虽然表示在书上看到过,但是具体确实没有用过,看到别人用了,虽然我也想用一下,但是还是觉得走正道吧,比较递归才是正道。不过这道题目,用了这个函数跑的比我的要快,6666
当然我也思考过我第一个为什么会T,原因就是我的排列是10个A的无序排列相乘,但是那种种还加了双重循环,所以T了。然后这里的话就是单纯的枚举一种,然后第二种就定了,所以只有排列组合的相乘。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cmath> 5 6 using namespace std; 7 const int inf = 0x3f3f3f3f; 8 const int maxn = 15; 9 int a[maxn]; 10 bool vis[maxn]; 11 int cnt; 12 int mini; 13 14 void minidfs(int l2, int tmp, int val2, int val1){ 15 if (l2 == 0){ 16 int t = abs(val2 - val1); 17 mini = min(mini, t); 18 return ; 19 } 20 for (int i = 1; i <= cnt; i++){ 21 if (vis[i]) continue; 22 if (val2 == 0 && a[i] == 0 && l2 != 1) continue; 23 vis[i] = true; 24 minidfs(l2 - 1, tmp / 10, val2 + tmp * a[i], val1); 25 vis[i] = false; 26 } 27 } 28 29 void dfs(int l1, int tmp, int val1){ 30 if (l1 == 0){ 31 int t = 1; 32 int l2 = (cnt + 1) / 2; 33 for (int i = 1; i < l2; i++) t *= 10; 34 //printf("%d ", l2); 35 minidfs(l2, t, 0, val1); 36 return ; 37 } 38 for (int i = 1; i <= cnt; i++){ 39 if (a[i] == 0 && val1 == 0 && l1 != 1) continue; 40 if (vis[i])continue; 41 vis[i] = true; 42 dfs(l1 - 1, tmp / 10, val1 + a[i] * tmp); 43 vis[i] = false; 44 } 45 } 46 47 int main(){ 48 int t; cin >> t; 49 getchar(); 50 while (t--){ 51 memset(vis, false, sizeof(vis)); 52 memset(a, 0, sizeof(a)); 53 cnt = 0; 54 mini = inf; 55 char ch = '0'; 56 while (ch != ' '){ 57 scanf("%c", &ch); 58 if (ch >= '0' && ch <= '9') a[++cnt] = ch - '0'; 59 } 60 int tmp = 1; 61 for (int i = 1; i < cnt / 2; i++) tmp *= 10; 62 //printf("%d ", tmp); 63 dfs(cnt / 2, tmp, 0); 64 printf("%d ", mini); 65 } 66 return 0; 67 }