伯乐在线编程挑战第 0 期 - 呼叫转移系统

如果你是第一次看到伯乐在线编程挑战,请点击这里查看《伯乐在线编程挑战简介》。

本期编程挑战的详细描述如下。

规则

编程语言无限制,提交周期是48小时。请在评论中提交代码。通过评论提交代码后不会立即公开,48小时过后,我们把大家的评论统一公开。更多规则请参见《伯乐在线编程挑战简介

特别注意:提交代码后,代码行前面的空格在显示时被清除。但后台仍然可以看到空格。发布之前,我们会把代码格式化后发布。如果你想自己提交时就格式化。请根据自己选择的语言,在代码前加上。代码结尾加上 pre 的闭合标签。

描述

呼叫转移服务是一个把呼叫号码A转移到号码B的服务。举个例子:当你正在度假时,这样的系统非常有帮助。A君度假去了,那么,A君的工作电话可以通过呼叫转移至B君。更进一步讲,当B君也正好在度假,还可以继续通过呼叫转移到C君,依次类推。也就是说,当一个客户打电话到A君,通过呼叫转移系统,最后转接到了C君。

本期的编程挑战是要实现一个和呼叫转移系统相关的逻辑。根据个人的度假时间安排和呼叫转移设置,返回呼叫转移的个数和“深度”。

输入

第一行给出一个整数N,代表从第二行开始有多少个度假安排。

每个度假安排为单独一行,其中包括4个数字:第一个数字是被叫人的4位数电话号码,第二个数字是呼叫转移至的4位数电话号码, 第三个数字是起始时间 ( 用天数计算),最后一个数字是度假时间的有效期(用天数计算)。

最后一行是开始日期。

请注意:
1) 这里的时间日期是基于天数顺序。1代表第一天,2代表第二天,依次类推。这里没有月份和年这样的时间单位,统一用天数来作为度假的日期安排。(天数最高是32位无符号整数的最大值)

2) 输入的呼叫转移不会出现环路。如描述中所举例, A君转到B君,B君再转到C君。但C君不会转到A君。对于有环路的输入,检测并提示输入环路错误,这点不作要求。当然,如果你的程序可以检测这种环路,并提示错误, 当然更好。

3)不能同时从一个号码转移到多个号码。如描述中所举例, A君转到B君,A君不能同时又转移到C君。

输出

基于开始度假的日期 (输入数据的最后一行), 你的程序必须打印输出2行信息。

1)当天设置了多少个呼叫转移
2)当天最长的呼叫转移是多长次 ( A君转到B君,B君再转到C君。这个是2次呼叫转移)

示例

(请注意:这个仅仅是示例数据,它们是为了方便大家理解题目而添加的,你的代码不能仅解析这5行示例数据)

1. 输入示例

2. 输出示例

//第 2 天为什么有 3 个呼叫转移?如果你没有看懂,这里解释一下: “ 0000 0001 1 3 ” 这个是3天有效,所以,第二天这个呼叫转移还有效。“0001 4964 2 1” 和 “4964 0005 2 3“ 都是第二天设置的,有效期分别是1和3天。所以,第 2 天共有 3 个呼叫转移设置。

收藏 160 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
  • PrM   2013/06/14

    • PrM   2013/06/14

      评论自动删除空格? 那没法发python了

      • 黄余粮 站长 2013/06/14

        稍等。正在处理......

      • 黄余粮 站长 2013/06/14

        Hi Prm,

        请在代码开始处添加:

        代码结尾添加:

        • rcgn   2013/06/14

    • PrM   2013/06/16

      我的代码被切掉了一些. 少了一个function..

      • 黄余粮 站长 2013/06/16

        不好意思,可能是我们的是失误。麻烦你直接在回复中贴上。我可以把这个函数加上。

  • nickcen   2013/06/14

  •   2013/06/14

    下面是我编程时的思路:
    这道题的编程不难,简单实现还是比较容易的,我主要考虑的是如何减少时间复杂度,能否在O(n)的时间内完成。我认为答案是肯定的。
    首先是录入数据,此处不多说。其次,使用了两个二维数组A[10000][2]和B[10000][2],数组A代表的是链出,数组B是链入,第一维中的数据是链入号码或链出号码,第二维是转移深度。A与B的大小均为10000,因为号码只有4位。如A[999][0]=222,A[999][1] = 2表示当天号码0999经过2次转移到号码0222;而B[222][0] = 999, B[222][1] = 2表示的是当天号码从0999经2次转移到号码0222。在求取当天转移次数及最大转移深度时,只需要一次循环即可完成。若当天有一条新的号码转移c->d被发现(即当天号码c经1次转移到d),先把它们加入到A和B数组中,然后在数组B中查找是否有号码转移到c(即B[c][1] == 0?),再在数组A中查找d是否转移到其它号码(即A[d][1] == 0?),若有,则修改数组中的值,并将转移次数相加。
    代码中for循环内的while可改成if,因为只需要在A,B中查找一次即可,即while循环最多只会执行一次,这是之前写代码时未仔细思考所致。因此,程序的时间复杂度是O(n),主要思想就是空间换时间。
    程序中未考虑环路及同一个号码转移多次的错误情况。这些情况其实比较容易判断,在发现一条新的转移路径时,加入数组前,判断数组中的转移次数是否为0,可判断同一号码多次转移;在数组A、B中查找相关转移时判断转移前后号码是否相同即可判断一路情况。
    上述描述如有错误,欢迎各位批评指正。

    • 企鹅   2013/06/16

      你好。跑了你的程序。 以下结果,我认为转移深度是4次。 0005在第二天没有假期,所以它接到4964的转移后,应该就停止转移了。 您跑出来的结果是3次。
      5
      0000 0001 1 3
      0001 4964 2 1
      4964 0005 3 3
      0005 3333 4 2
      3333 1212 2 4
      2

      • daniel   2013/06/16

        按照题意,你给的这组数字结果应该是2次转移吧。

      •   2013/06/16

        你给的这组数据,在第2天是有3组呼叫转移设置,分别是:0000->0001、0001->4964和3333->1212。其余两组在第2天根本就不会转移。故总共有3个转移,转移深度最大为2。
        ps:请注意,这里是第2天当天的转移,不包括第2天之后,只是当天。

  • scturtle   2013/06/14

  • aaron   2013/06/14

  • nico   2013/06/14

    这个题目有个不是很严谨的地方,小弟略提,请大牛指点。在成环的那个地方,题目中的要求不成环就可以,但是如果成环发生在一个人的休假结束以后,这个原则上应该是可以的吧。

    • 黄余粮 站长 2013/06/14

      谢谢提醒。

      环路发生在休假结束后,那其实就不是环路了。因为那条呼叫转移已经无效了。题目说的环路是指有效的呼叫转移之间的环路。

      • nico   2013/06/14

        也就是说,超过了一个人的休假日期,形成了环路,这种情况是允许的。写程序的时候,还要考虑这种情况,不能单纯的判断是否成环了。

        • 黄余粮 站长 2013/06/14

          是的。

          在这个题目当中,因为没有作明确要求,即使没有判断环路也可以。

          如果程序判断了环路,而且考虑这个情况,A++

          • 小狼医生   2013/06/15

            我是看了这条评论才意识到这个问题的,是不是有作弊嫌疑了。、。

            • 黄余粮 站长 2013/06/15

              你多虑了。如编程挑战发起的初衷中强调的那样,咱们不是来比高低的。而是通过参与其中 (分析问题,构思并写代码实现,阅读代码…… 更重要的是讨论交流)来提升自己分析和解决问题的能力。所以,动手写代码之前多讨论,可以把问题理解更清晰,其他参与的朋友也可以参考你分析问题的思路。另外,48小时内允许重复提交代码(替换之前提交的代码)。意味着大家可以参考评论,不断地改进之前的代码。我们的编程能力不就是在这种细微的重构中提升的么? :)

  • canjianx   2013/06/14

    • 程序猿预备党   2013/06/16

      为java顶一下,仅围观

    • 小狼医生   2013/06/16

      nice。用map其实也不错的,我之前想是用二维数组,后来不知道为什么放弃了,弄了个内部类封装。。

    • lunx   2013/06/16

      "0000 0001 1 3",
      "0001 4964 2 1",
      "4964 0005 2 3",
      "0011 0012 1 4",
      "0012 0013 2 3",
      "0013 0014 2 4",
      "0014 0015 1 5" 用这组数据测试 结果
      第 2 天共有 7个呼叫转移设置
      第 2 天最长的呼叫转移是 7 次
      两组以上不同呼叫转移链没有分别比较最深转移次数。

      • lunx   2013/06/17

        用这组号码也会有问题
        "0003 0005 2 3",
        "0001 0008 1 3",
        "0008 0003 2 1"
        第 2 天最长的呼叫转移是 5 次

        “0000 0001 1 3″,
        “0001 4964 2 1″,
        “4964 0005 2 3″, 用这一组数据会对,因为你的呼叫转移号码是从小到达,haspmap是有序的,callLength++ 凑巧一致

    • 黄中均   2013/06/17

      Map真心用的不错,看了代码发现自己的有很多需要学习的地方。

  • 一个人练习一个人说一个人真好   2013/06/14

  • wheat   2013/06/14

    刚提交的代码有错, 需要修改下

  • wheat   2013/06/14

  • 过来看看情况

  • 10iii   2013/06/14

  • JWZH   2013/06/14

    不存在既能从A转移到B,又能从A转移到C的情况吧

    • 黄余粮 站长 2013/06/14

      问的好! 这种情况不能同时存在。请忽略吧。题目当中确实没有强调这点,刚才补充说明了。

  • jaice   2013/06/14

    先围观下。。。明天提交代码

  • 高盐   2013/06/14

    鸡蛋里挑骨头:
    1、天数最高是32位无符号整数的最大值,这个考虑有点欠妥,人平均寿命就算100年,不过才3W多天,认为使用16位无符号整数的最大值表示就足够了。题目中使用32位无符号仅仅是为了增大系统开销还是…… ?
    2、对于有环路的输入,检测并提示输入环路错误,这点不作要求。作为一个可用的呼叫转移系统应该判断是否有环,而且还应该判断是否断链。样本中的数据在第3天就出现了断链的情况。不判断环路和断链是否是为了降低编程难度…… ?

    • 黄余粮 站长 2013/06/14

      挑的好啊!越来越有趣了。

      1) 你说的对。32位确实太长,16位更合适。
      2) 是的。确实是为了降低难度。环路、断链以及多重选择,在题目中都没有作检测要求。看看大家在写代码时,能不能主动添加上。

      谢谢高盐!

      • 小狼医生   2013/06/14

        环路倒好说,没有基础数据断链无法做啊。如果只录入一条呼叫转移数据,那必定是断链的节奏啊。。何解?

        • 高盐   2013/06/15

          只有一条怎么会叫断链呢,如果作为一个呼转系统,就单独一天而言,最合理的情况就是呼转的设置个数和呼转的次数(深度)是一致的。也就是从第一个电话不重复不间断的呼转到最后一个电话上。
          如果不能达到此目标,既证明呼转有问题,不能从最初始的电话转移到最终的目标电话号码上。
          单纯计算呼转的深度其实没有意义。因为如果呼转设置的次数为N,(排重之后也应该是N,如果不是那就说明有重复设置。)那最大呼转次数也一定是N。如果计算下来出现小于N就说明有断链,如果大于N就是有环。

          不好意思,又开始挑毛病了。

          • 小狼医生   2013/06/16

            大于N有环,这个我也认同。但小于N就说明断链,似乎不应该吧。我的意思是这样:假设有一些指定的电话号码在他们之间来回的转接,设置N条数据,其中某一个转接1次就找到目标了,就OK了,不说明任何问题。要是设置了一条范围之外的转接号码,那就断了找不到目标了。我是这个意思,不知道你的思路是。。?

  • yan   2013/06/14

    哪里提交代码?

  • Radec Zhang   2013/06/14

  • JWZH   2013/06/14

    抱歉,没加格式化,能把我原来那个删掉么

  • JWZH   2013/06/14

    • 企鹅   2013/06/16

      5
      0000 0001 1 3
      0001 4964 2 1
      4964 0005 2 3
      0005 3333 4 2
      3333 1212 2 4
      2

      测试说有circle

  • smartegg   2013/06/14

    简单说一下自己的思路。每个人看做点, A呼叫转移到B 看做是有向边 A->B.
    如此建图可以得到一个有向无环图, 原问题求的就是在这有向无环图的最长路。
    有向无环图求最长路 复杂度是 O(E)的:
    具体做法是按照拓补排序的顺序求 dp[v] = max(1+dp[u], dp[v])
    (其中dp[v] 表示以v 为终点的最长路, 并且 u->v 有边)

    #include 
    #include 
    #include 
    #include 
     
    namespace smartegg {
     
    using namespace std;
     
    class Graph
    {
    public:
        Graph(size_t maxVertices)
            : maxVertices_(maxVertices), edges_(0), adjList_(maxVertices_)
        {
     
        }
     
        void addEdge(size_t u, size_t v)
        {
            if (u >= maxVertices_ || v >= maxVertices_)
                throw invalid_argument("illegal input");
            adjList_[u].push_back(v);
            edges_ ++;
        }
     
        vector topologialSort()
        {
            vector Q(maxVertices_);
            vector inDeg(maxVertices_, 0);
            vector inQ(maxVertices_, false);
     
            int qs = 0, qt = 0;
            for (auto& vec : adjList_)
            {
                for (auto& v: vec)
                {
                    inDeg[v]++;
                }
            }
     
            for (int i = 0; i < maxVertices_; ++i)
            {
                if (inDeg[i] == 0)
                {
                    Q[qt++] = i;
                    inQ[i] = true;
                }
            }
     
            while (qs != qt)
            {
                size_t u = Q[qs++];
                for(auto& v: adjList_[u])
                {
                    if (--inDeg[v] == 0)
                    {
                        Q[qt++] = v;
                        inQ[v] = true;
                    }
                }
            }
            auto f = [](bool v) { return v == false;};
            if (any_of(inQ.begin(), inQ.end(), f) || Q.size() != maxVertices_)
                throw invalid_argument("the graph is  not a DAG!");
            return std::move(Q);
        }
     
        size_t edges() { return edges_;}
     
        vector<vector > adjList() { return  std::move(adjList_);}
     
    private:
        size_t maxVertices_;
        size_t edges_;
        vector<vector > adjList_;
    };
     
     
    class Solution {
    public:
        void prepareData() {
            cin >> N;
     
            for(size_t i = 0; i > tmp.left >> tmp.right >> tmp.startDay >> tmp.duration;
                data_.emplace_back(tmp);
            }
     
            cin >> checkDay;
        }
     
        void solve()
        {
            //first prepare the table which  can map the  phone number to small integers
            vector table;
     
            for(size_t i = 0; i= entry.startDay && checkDay <= entry.startDay + entry.duration - 1)
                    graph.addEdge(entry.left, entry.right);
            }
     
     
            auto toporder = graph.topologialSort();
            auto adjList = graph.adjList();
     
            //calculate longest path in DAG use dp
            vector dp(table.size(), 1);
     
            size_t total = 0;
            for(int i = 0; i < toporder.size(); ++i)
            {
                int u = toporder[i];
                for(auto& v : adjList[u])
                {
                    dp[v] = std::max(dp[u] + 1, dp[v]);
                }
            }
     
            cout << "第 " << checkDay << " 天共有 " << graph.edges()<< " 个呼叫转移设置"<< endl;
            cout << "第 " << checkDay << " 天最长的呼叫转移是 " << *max_element(dp.begin(), dp.end())  - 1 << " 次"<< endl;
        }
     
    private:
        int N, checkDay;
        struct Entry {
            size_t left, right;
            size_t startDay, duration;
        };
        vector data_;
    };
     
    }
     
     
     
     
    int main()
    {
        using namespace smartegg;
        Solution sol;
     
        sol.prepareData();
        sol.solve();
        return 0;
    }

  • garfee   2013/06/14

  • 一个人练习一个人说一个人真好   2013/06/14

    花了一中午时间敲的C代码,本人新手,求指点。

    • 黄余粮 站长 2013/06/14

      先感谢参与!你提交的代码已经看到了。后天中午12:00 前会统一公开全部的代码。大家相互学习。

  • Jerry   2013/06/14

    • 陈佳伟   2013/06/16

      没仔细看,但countCallDivert函数里面count和longest的值始终一致,也就是总共多少个转移和最长的次数一样,这应该是不对的吧。最长的次数不一定等于转移数。

    • lunx   2013/06/17

      checkCallDivert 方法判断没什么作用,countCallDivert方法 count++; longest++; 好像没什么区别。单组都算不出来最大转移深度。

  • 噪音   2013/06/14

    额.. 软件系大一学生表示还是先围观好了...

  • 写伪代码行吗?? 哈哈

  • Debug   2013/06/14

  • 小明同学   2013/06/14

    循环检测这个还是挺难得,考虑了下,A-->B-->C-->A咋一看算循环,
    但如果下面这种应该算是正常的输入
    第一天A-->B-->C,
    第二天C互转到A,但是A不再呼转到B

  • 小狼医生   2013/06/14

    java代码是这个节奏吗?

    • 小狼医生   2013/06/16

      My god...除了下边有位FEE仔同学300多行代码之外我在没看到比我多的了。。。貌似150+的都没再有了

      为什么java写出来要这么长的

    • 小狼医生   2013/06/16

      fucking stupid input and input checks,cost so many lines,i could have made it simple!!!

      • benjaH1   2013/06/18

        不用烦躁 在我看来input check也是很重要的 Never believe what user type in。。。

  • shunruo   2013/06/15

    思路:
    loop {
    从“呼叫转移”库提取当日开始的呼叫转移任务;
    计算并输出当时有效的呼叫转移数量与深度;
    日期更新(累进);
    清除过期的任务;
    } loop_end
    计算呼叫转移深度时使用递归,用映射记录一个呼叫转移链上的号码,环路时中止。

  • Fee仔是个蛋疼佬   2013/06/15