8598 整除15 问题

古城微笑少年丶 2022-12-30 10:57 135阅读 0赞

8598 整除15 问题  
时间限制:300MS 代码长度限制:10KB  
提交次数:447 通过次数:103

题型: 编程题 语言: G++;GCC;VC

Description

问题描述：  
给定一个只包含数字\[0…9\]的字符串，求使用字符串中的某些字符，构建一个能够整除15的最大的整数。  
注意，字符串中的每个字符只能使用一次。

编程任务：  
求由给定字符串构建的能够整除15的最大整数。

输入格式

输入数据为一个只包含数字\[0…9\]字符串，字符串的长度为1~1000。

输出格式

将构建出的最大整数输出。

如果无法构建出能够整除15的整数，请输出  
“impossible”

输入样例

02041

输出样例

4200

题解：  
先来考虑如何删除最少最小数，能使得剩下数能被3整除。  
把0~9数分为如下几类：  
0，3，6，9： 这四种数不影响  
2，5，8： 除3余2  
1，4，7： 除3余1

有以下几种情况：

情况一：  
这个数上各位数字和除3余0。不用删除操作。

情况二：  
给定的数上各位数字和除3余1。那么只要删除余1的那一类数中最小的一个。（min1看下文代码）  
如果数串中没有余1的数，就删除余2那类中的最小的两个数。（min2，min3看下文代码）

情况三：  
给定的数上各位数字和除3余2。那么只要删除余2那类最小的一个数。（min1看下文代码）  
如果数串中没有余2的数，就删除余1那类中的最小的两个数。（min2，min3看下文代码）

最后，剩余的数串以最大的并且以满足整除5的要求输出。  
在0存在的时候，就按计数的顺序输出即可。如果在数串中没有0，则必须有个5放在个位。

①string str;
    	②遍历一遍str，ii记录有无0，ii = 1,表示有0;
    	 numKK记录5的个数；x记录str中余1的个数，y记录余2的个数。
        ③先判断有无0/5，有则继续判断有无3,否则直接输出Impossible。
        if(ii || numKK){
        
        	int min1 = 10, min2 = 10, min3 = 10;
            int i, j;//i用于遍历，j记录min1的位置。
            int k, d;//记录min2，min3的位置。
            if(count % 3 == 1){
        
            	//删除余1最小的数。
                //若无余1，则删除余2最小的两个。
                //这里要注意的是，如果str中没有0，则要考虑数是5的情况。 若余2的数有5 5 8，删除两个最小的则删掉两个5，变得不符合题意。所以得保留一个5。然后删掉另外两个数。
            }else if(count % 3 == 2){
        
            	//删除余2最小的。（这里和上面一样，若str中余2的数只有 5和8，则删除的不是最小的，而是8。）
                //若无余2，则删除余1最小的两个。
            }else{
        
            	//对于count % 3==0
            	//str中有0则直接排序输出。
            	//没有0则，找一个5放最后，然后排序输出。
            }
        }else{
        
        	impossible;
        }

#include<iostream>
    #include<math.h>
    #include<algorithm>
    #include<string>
    
    using namespace std;
    
    bool cmp(char a, char b){
        
        return a>b;
    }
    
    int main(){
        
        string str;
        int count = 0; //数字总和
        int ii = 0,numKK = 0;//ii判断有无0,1表示有，numKK计算5的个数。
        int x = 0, y = 0;//x 余1的个数，y余2的个数。
        cin>>str;
        for(int i = 0; i < str.size(); i++){
        
            if(str[i] == '0')
                ii = 1;
            if(str[i] == '5')
                numKK++;
            if((str[i] - '0') % 3 == 1)
                x++;
            else if((str[i] - '0') % 3 == 2)
                y++;
            count += (str[i] - '0');
        }
    
        if(ii || numKK){
        
            int min1 = 10, min2 = 10, min3 = 10;
            int i, j;
            int k, d;//记录两个待删下标。
            if(count % 3 == 1){
        
                //删除余1最小的。
                //若无余1，则删除余2最小的两个。
                if(str.size() == 1){
        
                    cout<<"impossible"<<endl;
                    return 0;
                }
                for(i = 0; i < str.size(); i++){
        
                    int num = str[i] - '0';
                    if((num % 3) == 1 && num < min1){
        
                        min1 = num;
                        j = i;
                    }
                }
                if(min1 == 10){
        
                    if(str.size() == 2 ){
        
                        cout<<"impossible"<<endl;
                        return 0;
                    }
                    //有0删两最小余2.
                    if(ii){
        
                        for(i = 0; i < str.size(); i++){
        
                        int num = str[i] - '0';
                        if((num % 3) == 2){
        
                            if(min2 == 10){
        
                                min2 = num;
                                k = i;
                            }else if(min3 == 10){
        
                                min3 = num;
                                d = i;
                            }else{
        
                                if(min2 < min3){
        
                                    k = i;
                                    min2 = num;
                                }else{
        
                                    d = i;
                                    min3 = num;
                                }
                            }
                        }
                    }
                        // cout<<"min2: "<<min2<<"min3: "<<min3<<endl;
                        str[k] = '0';
                        str[d] = '0';
                        sort(str.begin(), str.end(), cmp);
                        for(int w = 0; w < str.size() - 2; w++){
        
                            cout<<str[w];
                        }
                        cout<<endl;
                        return 0;
                    }else{
        
                        if(y == 2){
        
                            cout<<"impossible"<<endl;
                            return 0;
                        }
                        //没有0，则最后留一个5，然后删两个最小余2。
                        for(int w = 0; w < str.size(); w++){
        
                            if((str[w] - '0') == 5){
        
                                swap(str[w], str[str.size() - 1]);
                                break;
                            }
                        }
                        for(i = 0; i < str.size() - 1; i++){
        
                        int num = str[i] - '0';
                        if((num % 3) == 2){
        
                            if(min2 == 10){
        
                                min2 = num;
                                k = i;
                            }else if(min3 == 10){
        
                                min3 = num;
                                d = i;
                            }else{
        
                                if(min2 < min3){
        
                                    k = i;
                                    min2 = num;
                                }else{
        
                                    d = i;
                                    min3 = num;
                                }
                            }
                        }
                    }
                        // cout<<"min2: "<<min2<<"min3: "<<min3<<endl;
                        str[k] = '0';
                        str[d] = '0';
                        sort(str.begin(), str.end() - 1, cmp);
                        for(int w = 0; w < str.size() - 2; w++){
        
                            cout<<str[w];
                        }
                        cout<<str[str.size() - 1]<<endl;
                        return 0;
                    }
                }else{
        
                    for(int w = j + 1; w < str.size(); w++){
        
                        str[w - 1] = str[w];
                    }
                    str[str.size() - 1] = '0';
                    sort(str.begin(), str.end(), cmp);
                    for(int w = 0; w < str.size() - 1; w++){
        
                        cout<<str[w];
                    }
                    cout<<endl;
                    return 0;
                }
            }else if(count % 3 == 2){
        
                //删除余2最小的。
                //若无余2，则删除余1最小的两个。
                if(str.size() == 1){
        
                    cout<<"impossible"<<endl;
                    return 0;
                }
                //如果只有一个5和一个其他余2的数，把5放最后，然后删掉那个余2的。
                //否则直接删除余2最小的。
                if(numKK == 1 && y == 2){
        
                    int t;
                    for(int w = 0; w < str.size(); w++){
        
                        if((str[w] - '0') == 5){
        
                            swap(str[w], str[str.size() - 1]);
                        }
                        if(((str[w] - '0') % 3 == 2) && (str[w] - '0') != 5){
        
                            t = w;
                        }
                    }
    
                    //覆盖t的值。
                    for(i = t + 1; i < str.size(); i++){
        
                        str[i - 1] = str[i];
                    }
                    sort(str.begin(), str.end() - 2, cmp);
                    for(i = 0; i < str.size() - 1; i++){
        
                        cout<<str[i];
                    }
                    cout<<endl;
                    return 0;
                }else{
        
                    //直接删除余2最小的。
                    for(i = 0; i < str.size(); i++){
        
                        int num = str[i] - '0';
                        if((num % 3) == 2 && num < min1){
        
                            min1 = num;
                            j = i;
                        }
                    }
                }
    
                //说明没有余2的数。直接删除两个最小余1的。
                if(min1 == 10){
        
                    if(x <= 2){
        
                        cout<<"impossible"<<endl;
                        return 0;
                    }
    
                    for(i = 0; i < str.size(); i++){
        
                        int num = str[i] - '0';
                        if((num % 3) == 1){
        
                            if(min2 == 10){
        
                                min2 = num;
                                k = i;
                            }else if(min3 == 10){
        
                                min3 = num;
                                d = i;
                            }else{
        
                                if(min2 < min3){
        
                                    k = i;
                                    min2 = num;
                                }else{
        
                                    d = i;
                                    min3 = num;
                                }
                            }
                        }
                    }
                        // cout<<"min2: "<<min2<<"min3: "<<min3<<endl;
                        str[k] = '0';
                        str[d] = '0';
                        sort(str.begin(), str.end(), cmp);
                        for(int w = 0; w < str.size() - 2; w++){
        
                            cout<<str[w];
                        }
                        cout<<endl;
                        return 0;
    
                }else{
        
                    //将j位置的元素删除，输出。
                    for(int w = j + 1; w < str.size(); w++){
        
                        str[w - 1] = str[w];
                    }
                    str[str.size() - 1] = '0';
                    sort(str.begin(), str.end(), cmp);
                    for(int w = 0; w < str.size() - 1; w++){
        
                        cout<<str[w];
                    }
                    cout<<endl;
                    return 0;
                }
            }
    
            //如果没有0,则5放最后，其他排序输出。
            if(ii == 0){
        
                int flag = 0;
                for(int i = 0; i < str.size(); i++){
        
                    if((str[i] - '0') == 5){
        
                        flag = 1;
                        swap(str[i], str[str.size() - 1]);
                        break;
                    }
                }
                if(flag){
        
                    sort(str.begin(), str.end() - 1, cmp);
                    cout<<str<<endl;
                }else{
        
                    cout<<"impossible"<<endl;
                }
            }else{
        
                sort(str.begin(), str.end(), cmp);
                cout<<str<<endl;
            }
        }else{
        
            cout<<"impossible"<<endl;
        }
        system("pause");
        return 0;
    }