PAT（甲级）1069 The Black Hole of Numbers (20point(s))

妖狐艹你老母 2024-05-08 05:54 18阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

如果n != 6174就一直迭代，迭代过程中把每个数拆分到一个数组中进行排序，二者做差，如果相等，提前结束迭代；否则继续迭代直到 n = 6174;  
**注意**，采用上述写法，如果一开始输入 6174 不会进入迭代，需要特判一下；  
此外，为了不重复写比较函数，这里借用了一个全局变量，根据 flag 的取值判断排序标准；

##### 代码 #####

#include <iostream>
    #include <string>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int maxn = 1e5 + 10;
    
    int flag = 0;
    
    bool cmp(int a, int b){
        
         //如果flag等于零，从大向小排，否则从小向大排
         if(flag == 0) return a > b;
         else return a < b;
    }
    //传入一个标志位，判断排序标准
    int helper(int n, int t){
        
         int ans = 0, i = 0;
         int c[5];
         memset(c, 0, sizeof(c));
         while(n > 0){
        
              c[i ++] = n % 10;
              n /= 10;
         }
         flag = t;
         sort(c, c + 4, cmp);
         for(int i = 0; i < 4; i ++) ans = ans * 10 + c[i];
         return ans;
    }
    
    int main()
    {
        
         int n;
         scanf("%d", &n);
         //注意6174是个特例
         if(n == 6174) {
        
              printf("7641 - 1467 = 6174\n");
              return 0;
         }
         while(n != 6174){
        
              int a = helper(n, 0);
              int b = helper(n, 1);
              if(a == b){
        
                   printf("%04d - %04d = %04d\n", a, b, a - b);
                   break;
              }
              else {
        
                   printf("%04d - %04d = %04d\n", a, b, a - b);
                   n = a - b;
              }
         }
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805400954585088