leetcode 第 217 场算法比赛

作者: | 更新日期:

线段树模板很重要

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

这次比赛有点难度,但是想想还是可以做出来的。

一、最富有客户的资产总量

题意:给出每个客户每个账号里的资产,求资产最大的客户的资产。

思路:每个客户得资产求和,取最大值即可。

源代码:
https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/217/A.cc

二、找出最具竞争力的子序列

题意:给一个长度为 n 的数组,求长度为 k 的子序列,使得子序列字典序最小。

思路:一个一个数字来看。

首先第一个数字可选的位置范围是 [1, n-k+1]
目标是选出这个范围的第一个最小值。

假设选择的是位置k1,则第二个数字的可选范围是 [k1+1, n-k+2]
目标依旧是选出这个范围的第一个最小值。

由此可以想到一个数据结构可以快速求区间最小值,即线段树。

我当是写了一个可以返回下标的最小值线段树通过了。

源代码:
https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/217/B.cc

赛后想,能不能使用更简单的方法来做呢?
毕竟这是 leetcode 的第二题,不能使用线段树这种 hard 级别的数据结构。

通过分析答案之间的关系,发现子序列的前半部分是递增的。
由此可以想到使用单调性这个性质来做这道题。

具体来说,对于前面可选的数据范围,数字需要保持单点非递减。
依据时 ,在可以任意选择的数字里面,后面遇到一个更小的数字,前面那些较大的数字不可能被选择,所以需要删除。

源代码:
https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/217/B02.cc

三、使数组互补的最少操作次数

题意:给一个长度为偶数的数组,每一次操作可以选择一个数字设置为[1,limit]之间的数字。
问最少需要多少次操作,才能使得所有的s[i] + s[n-i+1]的和相等。

思路:初步看这道题,只能想到枚举和,然后判断这个和的操作次数。
复杂度O(n^2)

枚举每个和,计算每对数字的代价,画出这个n*n的矩阵。
可以发现,对于每对数字,有一个和代价是0,两个区间的代价是1,两头的代价是 2。

另两个数字为 a 和 b 且 a<=b
具体公式如下

2: [b+limit+1, 2*limit]
1: [a+b+1, b+limit]
0: [a+b, a+b]
1: [a+1, a+b-1]
2: [2, a]

对于每个枚举和,我们其实是求矩阵一行的操作数和。
最终的目标是求最小的和。

这样,我们可以发现这是一个区间操作问题。

可以[2, 2*limit]区间,每个数字会对这个区间进行 5 个区间加相同值得操作。
最终求区间的最小值。

这个可以直接套用线段树或者树状数组解决。

源代码:
https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/217/C.cc

其实,对于若干区间加减操作,一次前缀和查询的场景,可以使用差分数组来解决。

差分的具体介绍大家可以看下面这个文档
https://oi-wiki.org/basic/prefix-sum/#_6

其实,树状数组的区间操作就是使用差分实现的。
后面我也会升级我的树状数组模板,支持区间操作。

四、数组的最小偏移量

题意:给一个数组,可以按下面的规则对数组的数字做任意次操作。

1)如果数字是偶数,可以除 2。
2)如果数字是奇数,可以乘 2。

问通过若干次操作后,使得数组里任意两个元素之间的最大差值最小。

PS:这里两个元素之间的最大差值误导了我,导致我理解错题意了。
我理解为求相邻的两个元素之间的差值最小。

思路:根据两个操作可以发现两个性质。

1)对于偶数,可以一直除,直到遇到奇数,顶多log(n)个。
2)对于奇数,只能乘一次,得到偶数,顶多 2 个。

由此,可以根据这两个性质,得到一个二维矩阵,每一行是数组中数字可以操作的数字。
矩阵的大小顶多为n * log(n)

我们的目标是从上到下选择一条路径,使得路径上的最大值与最小值差值最小。

对于奇数,可以证明,我们先预处理转化为偶数最优答案不变(可以操作无数次)。
所以这里可以先预处理输入,是的所有输入都是偶数,只能越操作越小。

预处理之后,所有数字只能越操作越小。
由于需要使最大值与最小值差值最小,那只能优先操作最大的值。
毕竟这样才有可能使最大的差值变小,

于是这道题的方法就出来了。

维护一个可以得到最大值和最小值的数据结构,不断的找到一个找到最大值做除 2 操作,并更新答案。
当最大值是奇数的时候,就不能再操作了。

我选择的数据结构是 set。

源代码:
https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/217/D.cc

当然,这道题也可以使用线段树来操作,即单点更新,区间查询。
具体方法是讲矩阵展开,即线段树有n log(n)个节点。
删除最大值的时候,就将对应下标的值设置为 无效,然后将另一个下标的值设置为除 2。

五、最后

这次比赛的题比较有质量,竟然遇到三个线段树,你可以用来练习线段树了。

PS:周六尝试参加了 atcode 比赛,从第一题开始,题目就看不懂。
以为是例外,看了第二题,题目依旧看不懂。
又看了第三题,还是看不懂。
最终花了好久才看懂这些题的含义,不过最后还是放弃比赛了。

加油,算法人。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越