[updated] hiho一下第91周《Events Arrangement》题目分析

18
11

题目大意

现在有一场持续时间为M的游乐会,在游乐会上有N种不同的表演节目,同一时间只能有一个节目进行表演。

每种节目最多可以表演K次,且每种节目具有自己的三个属性值a[i],b[i],c[i]

当一个节目在时间剩余p开始时,它会产生a[i]-(M-p)*b[i]的价值,这个节目会持续c[i]个单位时间。

此外由于最后有结束致辞,所以需要空出最后1个单位时间。

求问,怎么安排表演节目,可以使得产生的总价值最大。

解题思路

首先可以确定,本题是一道动态规划的题目。

每个物品计算其价值的函数为y = a[i] - (M - p) * b[i],在这个函数中只有p一个变量,其他均为常数。因此我们可以写成一个y关于p的函数:

y = f(p) = a[i] - M * b[i] + p * b[i]

f(p)由两个部分组成: - a[i] - M * b[i]是一个固定的值,只与活动本身的属性有关。记为A部分 - p * b[i]是随时间变化的值,与活动的开始时间有关。记为B部分

当我们已经选择好一系列活动之后,这些活动的A部分价值也就确定了。而我们要关心的是如何排序这些活动,使得B部分价值最大。

假设我们已经选好了k个活动,编号为1..k(注意,这里的编号和题目里面的种类序号不同)。记第i个活动开始的剩余时间为p[i],该活动对应的b值为b[i], c值为c[i]

B部分的总价值为:sigma(p[i]*b[i])

考虑能否找到一个性质,使得能够找到一种顺序使得B部分的值达到最优。

我们先来看看交换两个相邻的活动,会对结果造成怎么样的影响:

i,j是两个相邻的活动,i的剩余时间为p。由于交换i,j并不会影响到其他活动的开始时间,会改变的只有p[i]p[j]

交换前:

  • p[i] = p, p[j] = p - c[i]
  • v1 = p * b[i] + (p - c[i]) * b[j]

交换后:

  • p[i] = p - c[j], p[j] = p
  • v2 = (p - c[j]) * b[i] + p * b[j]

因此差值delta = v2 - v1:

delta = (p-c[j])*b[i] + p*b[j] - p*b[i] - (p-c[i])*b[j]
      = c[i]*b[j] - c[j]*b[i]

delta>0,则交换i,j可以使得B部分总价值最大。

delta>0换一个形式表示:

delta = c[i]*b[j] - c[j]*b[i] > 0
=> c[i]*b[j] > c[j]*b[i]
=> b[j]/c[j] > b[i]/c[i]

不妨设d[i]=b[i]/c[i],可以发现,若两个活动i,j相比,d值大的活动放在前面一定比较优。

又由于b,c均为活动本身的固定属性,每一种活动的d值也即是固定的。

因此我们得到一个性质:

将所有种类的活动按照b[i]/c[i]从大到小排序后,排名越在后面的活动越应该放在后面进行。


同时我们可以将原问题转化为一个背包问题。

把时间M看做背包的容积,N种活动看成N种不同物品。

由于每个活动的价值是跟开始时剩余时间P相关,可以理解成:当我们放入这个物品时,背包已使用的空间决定了这个物品的价值

因为后枚举的物品d值一定是最大的,所以我们假设这个物品就是最后放入背包的。

像这样一个物品的价值是由一个函数f(x)来决定的背包问题,我们称它为泛化物品背包问题

同时在本题中每一个活动可以选择K次,因此我们需要枚举放入几个该物品,像这样的问题我们称为多重背包问题

所以本题实质是一个多重泛化物品背包问题

一个解决的伪代码为:

sort() // 将活动按照b/c的值,从大到小排序
For i = 1 .. N // 枚举活动种类
    For v = c[i] .. M-1 // 枚举背包容量
        For j = 1 .. K // 枚举举办次数
            totalTime = c[i] * j
            If (totalTime > v) Thne
                // 举办j次,超过了背包容量
                Break
            End If
            tempValue = calc(v - totalTime, j, i)
            // 计算从v - totalTime开始连续进行j次活动i的得到的价值
            // 这个可以用数学方法进行计算,因此时间复杂度为O(1)
            If (f[i][v] < f[i - 1][v - totalTime] + tempValue) Then
                f[i][v] = f[i - 1][v - totalTime] + tempValue
            End If
        End For
    End For
End For

该算法在时间复杂度O(KMN),对于题目给出的数据范围,可以肯定会超过时间限制,还需要进一步优化。


在上面的循环中,我们枚举了最后一次活动结束时间,也即是背包容量v。由于每一次活动持续的时间均为c。因此固定v之后,我们考察的f[i-1][v']+tempValue中的v'一定是v减去整数倍的c,即:

v' = v - k*c (k≥1)

v'排序,并加上v刚好构成一个序列:v-k*c,v-(k-1)*c, ... , v-2*c, v-c, v

这个数列的值有一个共同的特点,就是他们模c同余。

所以我们不妨用一个数组q[r][]来按顺序记录所有模cr的容量v

将这个改动放入伪代码中为:

sort() // 将活动按照b/c的值,从大到小排序
q[][] = 0 // 将q[]设置为0
tail[] // tail[r]表示q[r]中保存的数字个数

For i = 1 .. N // 枚举活动种类
    tail[] = 0 // 将tail数组重置
    For v = c[i] .. M-1 // 枚举背包容量

        r = v % c[i]    // 得到余数r
        tail[r] = tail[r] + 1
        q[r][tail[r]] = v   // 将v放置于当前数组的最后一位

        t = tail[r] - 1
        while (t > 0 && (v - q[r][t]) / c <= K)
            // 检查到该时间点,活动举办的次数是否大于K
            tempValue = calc(q[r][t], v, i)
            // *注意这里计算价值函数改变了*
            // 计算从q[r][t]开始连续到时间v,连续进行活动i的得到的价值
            // 这个可以用数学方法进行计算,因此时间复杂度为O(1)
            If (f[i][v] < f[i - 1][ q[r][t] ] + tempValue) Then
                f[i][v] = f[i - 1][ q[r][t] ] + tempValue
            End If
        End While
    End For
End For

再加入q[r][]之后,我们可以通过这个数组来观察每个转移点v'f[i - 1][v']+tempValue,不妨用直方图来表示每一个v'所对应的f[i - 1][v']+tempValue

每一个蓝色的矩形对应了这个点的f[i-1][v']+tempValue值。

当我们枚举到v+c时,计算v'转移到v+c等于计算了v'转移到v再加上v~v+c这段时间进行了一次i活动。因此对于v+c的图来说,等于是在上图的基础上,全部增加一个相同的a[i]-(M-v)*b[i](橙色的部分):

可以观察到,在处理v时,选择v-c的值是优于v-2c的。即使v-c的值等于v-2c,也因为v-c举行的活动次数较少,而认为v-c更优。同理,在处理v+c时,v-cv-2c的相对大小也没有变化,v-c仍然优于v-2c。因此v-2c在得到v-c之后,无论如何都不会再用到。所以此时我们可以抛弃掉v-2c这个点。同样的还有v-4c这样的点。

当我们将所有类似v-2cv-4c的点都删去之后,可以得到图:

对于新的这个图,它有如下的性质: - 满足严格的单调性 - 任意一个v,其左边的点都是在计算它时需要枚举的点

我们可以通过计算相邻两个v'的值,去维护q[r][]满足这个单调性。而满足这种单调性的队列,我们称之为单调队列

在维持单调队列的情况下,枚举到某个v时,最优的结果显然就是最左边的点。因此我们不需要去从右到左依次枚举每一个可能的转移点,而直接选取最左的点即可。查找转移点的时间复杂度从O(K)降低至O(1)

并且由于每个转移点只会进一次单调队列,出一次单调队列。所以维护单调队列的均摊时间复杂度为O(1)

此外还需要注意,在本题中由于每个活动最多只能举行K次,所以转移点最多只能是v-k*c。所以我们除了需要维护队列末尾的tail之外,还需要一个维护队列头的head。当q[r][head[r]]的值小于v-k*c时,需要将head进行右移。

因此加入维护单调队列代码之后的伪代码为:

sort() // 将活动按照b/c的值,从大到小排序
q[][] = 0 // 将q[]设置为0
tail[] // tail[r]表示q[r]中保存的数字个数

For i = 1 .. N // 枚举活动种类
    tail[] = 0 // 将tail数组重置
    head[] = 1 // 将head数组重置为1
    For v = c[i] .. M-1 // 枚举背包容量

        r = v % c[i]    // 得到余数r
        tail[r] = tail[r] + 1
        q[r][tail[r]] = v   // 将v放置于当前数组的最后一位

        while (tail[r] > head[r]) {
            tempValue1 = calc(q[r][ tail[r] ], v, i)
            // 计算从q[r][ tail[r] ]开始到时间v一直进行活动i的得到的价值
            // v - q[r][ tail[r] ] 一定能够整除c
            value1 = f[i - 1][ q[r][tail[r]] ] + tempValue1

            tempValue2 = calc(q[r][ tail[r]-1 ], v, i)
            value2 = f[i - 1][ q[r][tail[r]-1] ] + tempValue2
            // 同样计算出前一个点

            If (value1 >= value2) Then
                // 可以抛弃tail[r]-1这个点了
                q[r][ tail[r] - 1 ] = q[r][ tail[r] ]
                tail[r] = tail[r] - 1
                // 用tail[r]覆盖掉原来的tail[r]-1
            Else
                Break
                // 该处满足单调性质,由于前面一直用同样的方法处理
                // 所以前面的部分也满足单调性质,因此可以直接退出循环
            End If
        }

        While ((v - q[r][ head[r] ]) / c[i] > K)
            head[r]++
            // 处理左边边界
        End While

        tempValue = calc(q[r][ head[r] ], v, i)
        f[i][v] = f[i - 1][ q[r][head[r]] ] + tempValue
    End For
End For

Result = max(f[N][])
// 最优值是f[N][0 .. M-1]中最大的一个

由此,整个算法的时间复杂度降低为O(NM),空间复杂度为O(NM)。对于给定的数据范围也就能够顺利通过了。

13 answer(s)

1

又是逻辑分析 智力题,神题 我做不出来 只能看看分析了

0

我想问一下……我投的是ux design,也收到了这个邮件,可是我看内容都是编程类的呀,有小伙伴知道设计岗位的笔试是怎么回事吗??求助!!谢谢!!

  • 据微软HR说ux design的成绩只作参考

  • 谢谢

  • 完全不会编程啊,申请的是PM,对这个要求很高吗?

  • 添加评论
  • reply
0

woc

1

OTZ

1

更新了前面对节目顺序的分析。
昨天的版本把 剩余时间开始时间 搞反了。

0

我刚学C语言,表示啥也看不懂

0

看了 就是换位思考法把这道题简化出来 让他通过等量代换 再求答案 不错的 挺经典的一道题

0

我就想知道,为什么只需要考虑 B 部分,虽然 A 部分是固定属性?比如对于 i、j 两个节目,对于 A、B两部分,若 i 的 B 部分小于 j 的B部分,但 i 的 A 部分远远大于 j 的 A 部分呢?

0

While ((v - q[r][ head[r] ]) / c[i] > K) { ... }应该是 While ( head[r] <= tail[r] && (v - q[r][ head[r] ]) / c[i] > K) 吧

0

看不进去。。。。 完全不想看!!!

0

投的PM。收到测试邮件时懵了

0

为啥设计师岗位还要编程测试

0

好题, 说到底, 第一步先分析出排序局部最优性质, 转化成一个多重背包的问题。 第二步就是多重背包使用单调队列优化。

write answer 切换为英文 切换为中文


转发分享