PTA-乙级-1019.数字黑洞

Contents

1. 输入格式：
2. 输出格式：
3. 输入样例 1：
4. 输出样例 1：
5. 输入样例 2：
6. 输出样例 2：

1019 数字黑洞（20 分)

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。

例如，我们从6767开始，将得到

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
… …

现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。

输入格式：

输入给出一个 (0,104) 区间内的正整数 N。

输出格式：

如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。

输入样例 1：

6767

输出样例 1：

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174

输入样例 2：

2222

输出样例 2：

2222 - 2222 = 0000

分析：

把输入当作string处理可以很轻松用sort函数进行自身的升序和降序操作。sort比较常用在string和vector上具体用法如下：

1.排列string（默认升序,可以用cmp进行降序排列）2.排列vector 3.排列数组 4.根据结构体中的参数按要求排列结构体（比如1015.德才论）

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
bool cmp(char a,char b){return a > b;}
int main()
{
    string s = "2345967801";
    int myints[] = {32,71,12,45,26,80,53,33};
    vector<int> myvector (myints, myints+8);
    sort(s.begin(),s.end());   // 0123456789 字符串升序排列
    sort(s.begin(),s.end(),cmp);  //9876543210 字符串降序排列
    sort(myvector.begin(), myvector.begin()+4);  //12 32 45 71)26 80 53 33 
    sort(myints,myints+8);  //12 26 32 33 45 53 71 80 数组升序排列
    return 0;
}

还有一个需要注意的点是不满四位数自动补全，可以用insert函数。下面的图来自https://www.cnblogs.com/meihao1203/p/9670680.html，是我看到的比较全的insert用法，常用的有：

1.s.insert(int a,int b,char z) //在s[a]处插入b个z字符

2.s.insert(int a,string str);//在s[a]处插入str

3.s.insert(int a,string str,int b);//在s[a]处插入str的前b位

4.s.insert(int a,string str,int b,int c);//在s[a]处插入str[b]及其之后一共c个字符

asic_string& insert( size_type index, size_type count, CharT ch ); 在index位置插入count个字符ch	string str = “meihao”;string sstr = str.insert(0,2,’a’);cout<<sstr<<endl; //aameihao
basic_string& insert( size_type index, const CharT* s ); index位置插入一个常量字符串	string str = “meihao”;string sstr = str.insert(1,”hello~~“);cout<<sstr<<endl; //mhello~~eihao
basic_string& insert( size_type index, const CharT* s, size_type count ); index位置插入常量字符串中的count个字符	string str = “meihao”;string sstr = str.insert(1,”hello~”,3);cout<<sstr<<endl; //mheleihao
basic_string& insert( size_type index, const basic_string& str ); index位置插入常量string	string str = “meihao”;string sstr = str.insert(1,str);cout<<sstr<<endl; //mmeihaoeihao
basic_string& insert( size_type index, const basic_string& str, size_type index_str, size_type count );index位置插入常量str的从index_str开始的count个字符	string str1 = “meihao”;string str2 = “hello~~“;string sstr = str2.insert(6,str1,3,3);cout<<sstr<<endl; //hello~~hao
basic_string& insert( size_type index, const basic_string& str, size_type index_str, size_type count = npos);index位置插入常量str从index_str开始的count个字符，count可以表示的最大值为npos.这个函数不构成重载npos表示一个常数，表示size_t的最大值，string的find函数如果未找到指定字符，返回的就是一个npos	string str1 = “meihao”;string str2 = “hello~~“;string sstr = str2.insert(6,str1,3,string::npos);cout<<sstr<<endl; //hello~~haocout<<string::npos<<endl; //4294967295
iterator insert( iterator pos, CharT ch ); iterator insert( const_iterator pos, CharT ch );	string str1 = “meihao”;string::iterator it = str1.insert(str1.begin(),’a’);// string::iterator it = str1.insert(str1.cbegin(),’a’); //第二种cout<<str1<<endl; //ameihaocout<<*it<<endl; //a
void insert( iterator pos, size_type count, CharT ch ); 迭代器指向的pos位置插入count个字符ch	string str1 = “meihao”;str1.insert(++str1.begin(),2,’a’);cout<<str1<<endl; //maaeihao
iterator insert( const_iterator pos, size_type count, CharT ch ); 迭代器指向的pos位置插入count个字符ch	string str1 = “meihao”;string::iterator it = str1.insert(++str1.cbegin(),2,’a’); //和上面的可以混用cout<<str1<<endl; //maaeihao
void insert( iterator pos, InputIt first, InputIt last ); iterator insert( const_iterator pos, InputIt first, InputIt last );	string str1 = “meihao”;string str2 = “hello”;//string::iterator it = str1.insert(str1.begin(),str2.begin(),str2.end());string::iterator it = str1.insert(str1.begin(),std::begin(str2),std::end(str2));cout<<str1<<endl; //hellomeihaocout<<*it<<endl; //h

代码：

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(char a,char b){ return a > b;}
int main()
{
    string s,a,b;
    int n;
    cin >> s;
    if (s[0] == s[1] && s[0] == s[2] && s[0] == s[3] ){
        cout << s << " - " << s << " = 0000";
        return 0;
    }
    do {
        s.insert(0,4-s.size(),'0');
        string a=s,b=s;
        sort(a.begin(),a.end(),cmp);
        sort(b.begin(),b.end());
        n = stoi(a)-stoi(b);
        s = to_string(n);
        s.insert(0,4-s.size(),'0');
        cout << a << " - " << b << " = " << s ;
        if (n!=6174) cout << endl;
    }while (n!=6174);
    return 0;
}