【算法作业】实验三：划分集合 - 贪心 & 可能的 IP 地址 - 回溯

2022 年 10 月 08 日
湖南
本文字数：3608 字
阅读完需：约 12 分钟

第一题：划分集合

1.题目

给定一组整数（它可以包含相等的元素）。你必须把它分成两个子集 A 和 B（它们都可以包含相等的元素或是空的）。你必须使 mex（A）+mex（B）的值最大化。这里集合的 mex 表示集合中不存在的最小非负整数。例如：mex（{1,4,0,2,2,1}）=3mex（{3,3,2,1,3,0,0}）=4mex（∅）=0（mex 为空集合）输入输入由多个测试用例组成。第一行包含一个整数 t（1<=t<=100）——测试用例的数量。测试用例的描述如下。每个测试用例的第一行包含一个整数 n（1<=n<=100）表示集合的大小。每个测试用例的第二行包含 n 个整数 a1，a2，…an（0<=ai<=100）表示集合中的数字。输出对于每个测试用例，打印 mex（A）+mex（B）的最大值。460 2 1 5 0 130 1 240 2 0 161 2 3 4 5 65340 注意在第一个测试用例中，A={0,1,2}，B={0,1,5}是一个可能的选择。在第二个测试用例中，A={0,1,2}，B=∅是一个可能的选择。在第三个测试用例中，A={0,1,2}，B={0}是一个可能的选择。在第四个测试用例中，A={1,3,5}，B={2,4,6}是一个可能的选择。

2.问题分析和算法设计思路

初看这个题目，很容易产生一个暴力的想法：尝试所有的划分情况，计算它们的 $m e x (A) + m e x (B)$ 的值，然后进行比较。但这样算法的时间复杂度就太大了，因为一个集合的子集数量，随集合的大小 n 是呈指数式变化的。

这个问题可以采用贪心算法的思路分析：

假设初始有两个空的集合 A、B，而输入的一组整数已经按照非递减的顺序排列好。现在我们需要从这一组整数的第一个数开始，逐个整数取出并放到 A、B 两个集合中的一个里。现在思考一下：如何放才能让 $m e x (A) + m e x (B)$ 的值最大化呢？

我们每次将一个数放入集合中，产生的效果可以分为两种：

$m e x (A) + m e x (B)$ 的值增加 1
$m e x (A) + m e x (B)$ 的值不变

为了进一步简化我们的问题，我们可以假设：这组非递减的整数是连续的。为什么能够做出这样的假设呢？因为如果某一处不连续，则从此处开始后面的整数将是无意义的。例如，考虑下面两组整数：

连续：1，2，3，4
不连续：1，2，3，4，6，7，8，9

显然，上面两组输入将得到相同的结果。即一组不连续的整数可以等效为另一组连续的整数的情况。

现在我们开始向两个集合中放数字。考虑如果我们遵守这样的规则：“每取一个数字，我们总是先考虑集合 A 的需求，当集合 A 中没有这个数字时，我们就将它放入集合 A；否则我们就将它放入集合 B。” 而这组整数又是连续的（前面假设），因此每次我们向集合 A 中添加元素，都将导致“ $m e x (A) + m e x (B)$ 的值增加 1”。于是我们就可以认为每次将元素放入 A 中都是值得的。

那有没有可能，我把某个元素放入 A 中时，虽然 $m e x (A) + m e x (B)$ 的值增加 1；但是如果把这个元素放到 B 中，在后来它将产生增加大于 1 的影响呢？答案是不能的。这里并不打算仔细讨论这个问题（可能我自己也还没有想的足够清楚）

注：采用贪心的思路，为确保我们每次局部最优的选择，在最终将导致全局最优的结果，我们的选择策略必须具备无后效性。

3.算法实现

前面我们的讨论中作出了“输入的整数已经有序”的假设。其实在无序的情况下，我们按照 “集合 A 优先” 的策略得到的效果也是一样的，并不需要先对整数进行排序操作。

实现代码：

#include<iostream>using namespace std;
int main(){    int t=0;//测试的组数    int n=0;//每组测试的数据量    int a[102]={};//存放数    int num1=0;    int num2=0;    int out[102]={};//存放输出         cin>>t;        for(int i=0; i<t; i++){        int mex1[102]={};//第一个集合         int mex2[102]={};        cin>>n;                //输入，同时划分集合         for(int j=0; j<n; j++){            //输入             cin>>a[j];                        //划分集合             if(mex1[a[j]] ** 0){                mex1[a[j]] = 1;            }            else if(mex2[a[j]] ** 0){                mex2[a[j]] = 1;            }        }                //得到最大值        for(int j=0; j<=n; j++){            if(mex1[j] ** 0){                num1 = j;                break;            }        }                 for(int j=0; j<=n; j++){            if(mex2[j] ** 0){                num2 = j;                break;            }        }                 //保存输出        out[i] = (num1 + num2);    }        //输出     for(int i=0; i<t; i++){        cout<<out[i]<<endl;    }        return 0;}

复制代码

4.运行结果

5.算法分析

算法的时间复杂度为： $o (n)$ ，对于每组测试数据，我们都只需遍历一次即可。

第二题：可能的 IP 地址

1.题目

给定一个只包含数字的字符串，通过返回所有可能的有效 IP 地址组合来恢复该字符串。有效的 IP 地址必须采用 A.B.C.D 的形式，其中 A、B、C 和 D 是 0-255 之间的数字。除非数字为 0，否则不能以 0 作为前缀。输入描述 输入第一行 n，为测试用例个数接下来 n 行，输入 n 个整数字符串如果可以分解为 ip，则输出所有可能的 ip，每个 ip 都要换行；如果不能分解，则输出一个-1。输入 2 25525511135 25505011535 输出 255.255.11.135 255.255.111.35 -1

2.问题分析和算法设计思路

可以采用回溯法的思路，输入与输出之间就差了三个小数点，我们只需找出小数点合法的位置即可。

如果一个数字串可以成为合法的 IP 地址，那么它一定是恰好有 3 个小数点。于是我们可以选择将小数点的位置作为回溯的对象（而不是去确定每个位置会不会有小数点），这样回溯就只有三层。

我们可以从前往后依次来尝试三个小数点的位置：先放第一个小数点，再放第二个小数点，在放第三个。每次放小数点时检查是否合法，不合法就回溯。

3.算法实现

代码：

#include<iostream>#include<cstdio>using namespace std;
const int BigNum = 999;
//将字符串，转化为整数 long long  str2num(char str[], int first, int end) {        int len = end - first + 1;    long long sum=0;        //非零整数的零前缀情况     if(len > 1 && str[first] ** '0') sum = BigNum;        for(int i=0; i<len; i++){        int num = str[first+i] - '0';        sum = sum * 10 + num;    }    return sum;}
int main(){    int n=0;//测试组数        cin>>n;    cin.get();//读取回车         //迭代不同的测试组     for(int i=0; i<n; i++){                char str[100]={};        int end[3]={};        int len=0;//字符串的长度         int flag=0;//是否有可能的ip地址             //输入一串数字        char temp=cin.get();                for(int j=0; temp != '\n'; j++){            str[j] = temp;            len++;            temp = cin.get();        }                 //数字太长则无法转为ip地址        if(len > 12) {            cout<<"-1"<<endl;             continue;        }                //开始        long long num=0;//字符串转整数                //迭代第一个小数点的位置         for(int j=0; j<len; j++){            end[0] = j;  
            num = str2num(str, 0, end[0]);             if(num > 255) continue;                        //迭代第二个小数点的位置             for(int k=j+1; k<len; k++){                end[1]=k;                                num = str2num(str, end[0] + 1, end[1]);                  if(num > 255) continue;                                //迭代第三个小数点的位置                 for(int l=k+1; l<len; l++){                    end[2]=l;                                        num = str2num(str, end[1] + 1, end[2]);                      if(num > 255) continue;                                        else if(str2num(str, end[2] + 1, len - 1) > 255) continue;
                    //成功输出结果                     else {                        for(int m=0; m<len; m++){                            cout<<str[m];                            if(m ** end[0] || m ** end[1] || m ** end[2]) cout<<".";                        }                         cout<<endl;                                                flag = 1;                    }                }            }        }                 if(! flag) cout<<"-1"<<endl;    }         return 0;}

复制代码

4.运行结果

5.算法分析

时间复杂度的准确分析会比较复杂，因为每一次小数点的放置都会改变其它小数点可选位置的数量，于是我放弃了。但它至少随着数字串长度的增加，时间复杂度应当是多项式级别，而非指数级别，因为小数点确定只有三个。

感谢阅读

博主主页：CSDN清风莫追

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/e4a764f86795b588513dbc22f】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景

【算法作业】实验三：划分集合 - 贪心 & 可能的 IP 地址 - 回溯

第一题：划分集合

1.题目

2.问题分析和算法设计思路

3.算法实现

4.运行结果

5.算法分析

第二题：可能的 IP 地址

1.题目

2.问题分析和算法设计思路

3.算法实现

4.运行结果

5.算法分析

清风莫追

评论