链接:https://ac.nowcoder.com/acm/contest/545/C
来源:牛客网
题目描述
出题人有两个数组 $A, B$,请你把两个数组归并起来使得 $Cost=∑i∗C_i$ 最小,要求两个原数组的顺序在新数组中保持不变。
输入描述
第一行输入两个正整数 $n,m$,分别表示数组 $A, B$ 的长度。
第二行输入 $n$ 个正整数,表示数组 $A$。
第二行输入 $m$ 个正整数,表示数组 $B$ 。
输出描述
一个正整数,表示最小代价 $Cost$。
示例 1
备注
$n, m \le 100000$
$A_i, B_i \le 100000$
解题思路
$O(nm)$ 动态规划很容易想到,但是复杂度太高且没有方法优化,那么就考虑贪心解法。
显然,合并后的数组 $C$ 格式为 $\dots ABABA\dots$,即一段 $A$ 接一段 $B$ 。
常见的贪心策略为,考虑相邻元素的交换是否会导致更优的结果。由于不能打乱原先的顺序,故总是后段的前缀替换前段的后缀,不失一般性,我们可以假设前段为 $A$,后段为 $B$。
记 $Cost(A) = \sum_{i = 1} ^ {|A|}i\times A_i$,则原先的贡献值为 $Cost(A)+Cost(B)+|A|\times Sum(B)$,交换后的贡献值为 $Cost(A)+Cost(B)+|B|\times Sum(A)$,则当 $|B|\times Sum(A) \lt |A|\times Sum(B)$,即
也就是说,均值越大的段需要优先选择。
剩下的就是如何构造这些段,我们假设串 $A=A_1A_2$,当 $Average(A_1)\lt Average(A_2)$ 时,在数组 $C$ 中总会合并成一段,根据这一性质在原数组中利用单调栈即可构造初始的段,之后就是从数组 $A,B$ 贪心选择均值较大的段。
1 |
|