整除15问题 | 贪心

小咪咪 2023-07-19 10:32 23阅读 0赞

> ## 整除15问题 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年03月30日 星期一 07:55</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年04月26日 星期日 23:55</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年04月26日 星期日 23:55</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 给定一个只包含数字 \[0..9\] 的字符串，求使用字符串中的某些字符，构造一个能够被15整除的最大整数。注意，字符串中的每个字符最多只能使用一次。 输入：程序从标准输入读入数据，每行数据由一串数字组成，长度为1到1000。 输出：针对每一行输入，输出一个结果，每个结果占一行。如果无法构造出能够被15整除的整数，请输出impossible。
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td> <p>&nbsp;</p> 
>     <ol> 
>      <li>1↵</li> 
>      <li>01431↵</li> 
>      <li>103↵</li> 
>     </ol></td> 
>    <td> <p>&nbsp;</p> 
>     <ol> 
>      <li>impossible↵</li> 
>      <li>43110↵</li> 
>      <li>30↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

### 思路 ###

被15整除不好直接判断，我们可以分开讨论：**一个数可以被3整除且可以被5整除，则可以被15整除**。

（为了方便处理，我将读入的字符串数组转到了vector容器中，如果用数组也是一样的实现，思路是一模一样的）

为了使得数字最大，我们应该**先对这串数字排序**再进行处理（贪心思想），排序操作直接调用sort函数即可，sort的具体使用看看这一篇文章[排序算法 | sort函数的使用][_ sort]~然后对于有序的序列，我们依次考虑：

**1、将数字处理为5的倍数**

写成一个函数，返回值为bool型，如果 本身是5的倍数/可以通过处理成为5的倍数 就返回true，否则返回false。

这又分两种情况：

**本身就是5的倍数**

序列的最后一位是0或5，直接返回true。

**本身不是5的倍数**

既然是有序的，末尾不是0或5，说明整个序列中没有0。可以证明，将序列中的5（任意一位）移至末位，即是满足为5的倍数这一条件的最大序列，处理完后返回true。如果整个序列中找不到5，那么这个序列不可能是5的倍数，返回false。

bool DivFive() {
        /* 本身就可以被5整除 */
        if (num.back() == 0 || num.back() == 5)
            return true;
        /* 找到5把它移到最末位上 */
        for (int i = 0; i < num.size(); i++)
            if (num[i] == 5) {
                num.erase(num.begin() + i);  //删除
                num.push_back(5);  //加入最后
                return true;
            }
        return false;
    }

**2、将数字处理为3的倍数**

写成一个函数，返回值为bool型，如果 本身是3的倍数/可以通过处理成为3的倍数 就返回true，否则返回false。写一个 **CalcSum函数 **计算所有项的和，设所有项的和对3取模的结果为tail。

/* 获取所有元素之和 */
    int CalcSum() {
        int sum = 0;
        for (int i:num)//依次访问num中的每一个元素i
            sum += i;
        return sum;
    }

接下来又分两种情况：

**本身就是3的倍数**

tail = 0，即所有项的和是3的倍数，直接返回true。

**本身不是5的倍数**

tail = 1 或 2，那么有两种处理方式，可以让序列和变成3的倍数：

1.  删除一个 模3同余(对3取模为tail) 的数，且这个数尽可能小
2.  删除两个 对3取模为 3 - tail 的数 ，且让这两个数尽可能小

为了让最后结果更大，贪心考虑：我们应该**优先考虑第一种方法**，找不到符合要求的数，再考虑第二种。且在每一种方法的实现时，要尽可能使得删除的数字小，由于我们序列已经是有序的了，那么我们应该**从倒数第二位向前遍历**（不能处理末位！！因为末位是序列为5的倍数的保证）

bool DivThree() {
        int tail = CalcSum() % 3;
        /* 本身就可以被3整除 */
        if (tail == 0)
            return true;
        /* 删除一个模3同余的元素（越小越好） */
        for (int i = num.size() - 2; i >= 0; i--)  //为保证最小且不破坏其能被5整除，从倒数第二项开始遍历
            if (num[i] % 3 == tail) {
                num.erase(num.begin() + i);
                return true;
            }
    
        tail = 3 - tail;
        int flag = 0; //记录找到的元素个数
        /* 删除两个模3余tail的元素（越小越好） */
        for (int i = num.size() - 2; i >= 0; i--) {  //为保证最小且不破坏其能被5整除，从倒数第二项开始遍历
            if (num[i] % 3 == tail) {
                num.erase(num.begin() + i);  //删除
                flag++; //记录一个
            }
            if (flag == 2)
                return true;
        }
        return false;
    }

--------------------

完整AC代码：

//
    // Created by A on 2020/3/30.
    //
    
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    
    #define MAXN 1005
    using namespace std;
    
    vector<int> num;
    
    /* 将输入的字符串数组转化成vector容器 */
    void getVector(char s[]) {
        for (int i = 0; i < strlen(s); i++)
            num.push_back(s[i] - '0');  //字符转换为数字
    }
    
    bool cmp(int x, int y) {
        return x > y;
    }
    
    /* 获取所有元素之和 */
    int CalcSum() {
        int sum = 0;
        for (int i:num)//依次访问num中的每一个元素i
            sum += i;
        return sum;
    }
    
    bool DivThree() {
        int tail = CalcSum() % 3;
        /* 本身就可以被3整除 */
        if (tail == 0)
            return true;
        /* 删除一个模3同余的元素（越小越好） */
        for (int i = num.size() - 2; i >= 0; i--)  //为保证最小且不破坏其能被5整除，从倒数第二项开始遍历
            if (num[i] % 3 == tail) {
                num.erase(num.begin() + i);
                return true;
            }
    
        tail = 3 - tail;
        int flag = 0; //记录找到的元素个数
        /* 删除两个模3余tail的元素（越小越好） */
        for (int i = num.size() - 2; i >= 0; i--) {  //为保证最小且不破坏其能被5整除，从倒数第二项开始遍历
            if (num[i] % 3 == tail) {
                num.erase(num.begin() + i);  //删除
                flag++; //记录一个
            }
            if (flag == 2)
                return true;
        }
        return false;
    }
    
    bool DivFive() {
        /* 本身就可以被5整除 */
        if (num.back() == 0 || num.back() == 5)
            return true;
        /* 找到5把它移到最末位上 */
        for (int i = 0; i < num.size(); i++)
            if (num[i] == 5) {
                num.erase(num.begin() + i);  //删除
                num.push_back(5);  //加入最后
                return true;
            }
        return false;
    }
    
    void print() {
        /* 特殊处理：当0打头时 */
        if (num.front() == 0) {
            printf("0\n");  //只输出一个0即可
            return;
        }
        /* 一般处理 */
        for (int i : num)  //从头到尾输出
            printf("%d", i);
        printf("\n");
    }
    
    int main() {
        char str[MAXN];
        while (EOF != scanf("%s", str)) {
            num.clear(); //一定一定记得清空容器
            getVector(str);  //将字符串储存在容器中
            sort(num.begin(), num.end(), cmp);  //降序排序
            if (DivFive() && DivThree())  //可以调整为15的倍数
                print();
            else  //不可以调整为15的倍数
                printf("impossible\n");
        }
    }

注意：

1.  在处理输出时，要记得将0单独处理。如果最后序列中最高位为0，那么整体应该直接输出0，而不是再继续依次输出每一位。比如4000，在经过 DivFive 和 DivThree 两个函数处理后序列变为 000，而应该输出0！！！
2.  每一次循环开始要清空容器！！！

--------------------

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]

[_ sort]: https://blog.csdn.net/weixin_43787043/article/details/104267119?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158554073219724811802510%2522%252C%2522scm%2522%253A%252220140713.130056874..%2522%257D&request_id=158554073219724811802510&biz_id=0&utm_source=distribute.pc_search_result.none-task
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/c41795dca6aa4a05ac6be637e9c33f4d.png