约束条件下最优化问题

Published: by Creative Commons Licence

  • Tags:

单调函数求和问题

题目1:给定$m$个线性函数$f_1,\ldots,f_m$,其中$f_i(x)=a_ix+b_i$,现在我们希望为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值,且要求满足$\max_{i=1}^mx_i=n$,在满足约束条件下,要求$\sum_{i=1}^nf_i(x_i)$尽可能大。

我们可以这样来理解这个问题,首先我们有$m$个可投资对象和$n$个资源,且已经获利$\sum_{i=1}^mb_i$,接下来如果我们为第$i$个可投资对象每投入一单位资源,那么就能获利$a_i$,问最大获利多少。

这个自然是将所有资源都砸在$a_i$最大的可投资对象上了。

题目2:给定$m$个函数$f_1,\ldots,f_m$,且每个函数的成像都构成一个上凸包,现在我们要求为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值,且要求满足$\sum_{i=1}^mx_i=n$,在满足约束条件下,要求$\sum_{i=1}^nf_i(x_i)$尽可能大。其中$1\leq m,n\leq 10^5$

利用题目1的方式,我们来试图重新解读问题。首先我们有$m$个可投资对象和$n$个资源,且已经获利$\sum_{i=1}^mf_i(0)$,接下来如果我们为第$i$个可投资对象每投入一单位资源,那么就能获利$f_i(x+1)-f_i(x)$($x$是已经向第$i$个可投资对象投入的资源总量),问最大获利多少。

我们会发现由于所有的函数都是上凸包,因此对于任意$i$,$d_i(x+1)=f_i(x+1)-f_i(x)$是非严格递减函数。考虑到$d_i(1)\geq d_i(2)\geq \ldots$,因此在最终结果中,如果选择$d_i(x+1)$那么我们必定也会选择$d_i(x)$,因此我们可以将所有可选的收益一开始就全部展开${d_i(x)}$,现在我们要做的就是从$d_i(x)$中选择正好$n$个元素,且元素之和最大。这个步骤自然我们会选择使用贪心算法来完成。

现在回到问题,如果我们把所有方案都展开,那么可能会有$nm$个选择,这样太多了,但是由于我们在取得$d_i(x)$之前是不会考虑$d_i(x+1)$的,因此我们可以对每个$i$,仅考虑$x$最小且未被选择的$d_i(x)$。实际操作中,我们只需要维护一个大小为$m$的大根堆即可,当我们将$d_i(x)$弹出的同时,将$d_i(x+1)$加回即可,总的时间复杂度为$O(n\log_2m)$。

提供一道SGU的问题

题目3:给定$m$个函数$f_1,\ldots,f_m$,且每个函数的成像都构成一个上凸包,现在我们要求为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值,且要求满足$\sum_{i=1}^mx_i=n$,在满足约束条件下,要求$\sum_{i=1}^nf_i(x_i)$尽可能大。其中$1\leq m\leq 10^5$,$1\leq n\leq 10^{18}$

这个问题是今天比赛的一道题目学到的。由于是上凸包,因此我们可以用三分算法为每个函数找到其极值点(在非负整数定义域下),记$f_i$的极值点在$p_i$处取到。

分两种情况讨论,如果$n\leq \sum_{i=1}^m p_i$,那么我们可以断定一定有$x_i\leq p_i$,否则对应的就有$x_i\geq p_i$。

如果是$n\leq \sum_{i=1}^m p_i$的情况。记$d_i(x)=f_i(x)-f_i(x-1)$称为函数$f_i$在点$x$处的增量。很显然最优解中,采用的最小增量一定是最大的,我们可以通过二分法找到这个最小增量,这里的时间复杂度为$O(n(\log_2M)^2)$,其中$M$是数据范围。找到最小增量$\delta$后,我们将$x_i$设置为$f_i$增量大于等于$\delta$的整数点数目(不包括0)。那么此时可能会有$\sum_{i=1}^mx_i>n$的情况出现,我们可以保证所有函数增量大于$\delta$的整数点都会被保留(否则为什么要使用增量为$\delta$的点呢?),而增量为$\delta$的点可以删除一部分,来满足$\sum_{i=1}^mx_i>n$,这一部分的时间复杂度为$O(m)$。

对于$n\geq \sum_{i=1}^m p_i$的情况,与上面的方法类似。

最后总的时间复杂度为$O(m(\log_2M)^2)$。

提供一道题目

未知数区间约束问题

题目1:给定$n$条非负未知数$x_1,\ldots,x_n$,以及$m$个条件。第$i$个条件选择一个区间$[l_i,r_i]$以及一个非负数$c_i$,并要求$\sum_{j=l_i}^{r_i}x_i\leq c_i$。在上述约束条件下,我们希望最大化$\sum_{i=1}^nx_i$,如果结果是无穷则输出$-1$。其中$1\leq n,m\leq 10^6$

这个问题可以这样来解决。首先我们可以发现在最优情况下$x_1$一定会取到最大,如果$x_1$未取到最大,则一种情况是$x_2,\ldots,x_n$都是$0$,这时候我们可以让$x_1$增加$1$,这与当前是最优情况相悖。第二种情况是存在一个最小的下标$j$,满足$1\lt j$且$x_j>0$,这时候我们让$x_j$减少$1$,同时让$x_1$增加$1$,重复这个过程直到$x_1$达到最大为止,可以发现这个过程不会导致任意约束条件被破坏。

因此具体的做法按照下标从小到大处理$x_i$,同时维护一个平衡树,平衡树中按照约束$c$排序,存储所有覆盖了$x_i$的约束。之后我们选择最小的约束$y$,并将$x_i$设置为$y$,并将平衡树中所有约束全部减少$y$。

至于无穷,如果我们发现某个未知数没有被约束,则结果为无穷。

这个做法的时间复杂度为$O((n+m)\log_2m)$。

题目2:给定$n$条非负未知数$x_1,\ldots,x_n$,以及$m$个条件。第$i$个条件选择一个区间$[l_i,r_i]$以及一个非负数$c_i$,并要求$\sum_{j=l_i}^{r_i}x_i\geq c_i$。在上述约束条件下,我们希望最小化$\sum_{i=1}^nx_i$。其中$1\leq n,m\leq 10^6$

类似问题1,这个问题也可以贪心解决。首先我们可以发现在最优情况下$x_1$一定会取到最小,如果$x_1$未取到最小,这时候我们让$x_2$增加$1$,同时让$x_1$减少$1$,重复这个过程直到$x_1$达到最小为止,可以发现这个过程不会导致任意约束条件被破坏。

这道题目的做法,就是遍历下标,当我们遍历到$i$的时候,找到所有右边界恰好为$i$的约束,将$x_i$设置为最大的约束值。这个过程可以通过维护前缀和来优化,总的时间复杂度为$O(n+m)$。

负重问题

题目1:给定$n$只骆驼,$m$条桥,骆驼需要经过这些桥。其中第$i$只骆驼的重量为$w_i$,第$i$个桥的长度为$l_i$,负重为$v_i$。你可以任意调整骆驼的先后顺序,并且为两只相邻骆驼赋予一个距离。现在希望骆驼队伍能顺利通过所有桥的前提下,最小化队伍头部骆驼和尾部骆驼的距离。如果有若干只骆驼之间最大距离小于$l_i$,且它们的总重量超过$v_i$,则它们不能通过桥$i$。其中$1\leq 8\leq n, 1\leq m\leq 10^5, 1\leq w_i,l_i,v_i\leq 10^9$。

原题

一开始想的是贪心让相邻骆驼距离尽可能接近,利用二分,对于每个排列的时间复杂度为$O(nm\log_210^9)$,但是可以发现实际上我们可以把二分去掉,时间复杂度为$O(nm)$,但是加上排列后时间复杂度为$O(n!nm)$,这个显然太慢了。

我们可以发现对于排列$1,2,\ldots,n$,如果某个距离分配无法通过,则必定存在一个区间$[l,r]$,以及某条桥$i$,区间中的骆驼的总距离小于$l_i$,但是总重量大于$v_i$。因此如果区间都满足桥的约束,则就能顺利通过所有桥。

事实上虽然$m$很大,但是可以发现每个区间$[l,r]$仅存在一个最大的约束条件,而如果通过预处理$m$条桥(桥的负重越大,长度也越大),我们这里可以$O(\log_2m)$得到具体的约束条件。这部分实际上是未知数区间约束问题的第二题,可以在$O(n^2\log_2m)$时间复杂度内解决。

总的时间复杂度为$O(n!n^2\log_2m)$。