程序员进阶之算法练习（三十一）

前言

BAT常见的算法面试题解析：

程序员算法基础——动态规划

程序员算法基础——贪心算法

工作闲暇也会有在线分享，算法基础教程----腾讯课堂地址。

正文

1.Mahmoud and a Triangle

题目链接

题目大意：

给出n个线段，每个线段长度为ai;

从中选出3个线段，组成一个三角形；

如果可以，输出YES；

如果不可以，输出NO；

输入数据：

第一行，整数n (3 ≤ n ≤ 1e5)

第二行，n个整数 a1, a2, ..., an (1 ≤ ai ≤ 1e9)

Examples

input

5

1 5 3 2 4

output

YES

input

3

4 1 2

output

NO

题目解析：

这个题的题意很清晰， 我们知道三角形的性质是：两边之和大于第三边；

暴力的做法是：枚举两条边，再遍历每一条边，通过上面的性质，判断是否为三角形；

但是因为n较大，暴力枚举不可行；

假设三条边分别是a,b,c，并且a<=b<=c，那么只需满足 a+b>c的条件即可；

那么先对数组a排序，然后枚举两条边，假设是ai和aj，且(i < j)

容易知道，对于第三条边，必然是aj+1；（证：如果存在k>j+1，且ai+aj>ak,那么必然有ai+aj>aj+1);

同理，我们知道j必然等于i+1；

这样我们可以知道，只需枚举i，就能知道另外两条边；

复杂度降到O(N);

思考🤔：

2. The Queue

题目链接

题目大意：

小明要去一个地方办业务，业务员上班时间是Ts到Td；

办业务的人很多，排成一列，业务员为每个人办业务都需要时间Tf;

已知n个人的到达时间ai；（ai为正整数，ai < ai+1 ）

小明可以在任何非负整数的时间到达，如果和其他人同时到达，小明会让其他人先，自己排队；

现在小明希望排队时间最短，问：他应该在哪个时间点到达；如果有多个答案，输出任何一个；

输入数据：

第一行 三个整数，Ts、Td和Tf（Ts和Td最大不超过1e12）

第二行，数字n (0 ≤ n ≤ 100 000)

第三行，n个数字，表示n个人的到店时间；

Examples

input

10 15 2

2

10 13

output

12

input

8 17 3

4

3 4 5 8

output

2

题目解析：

从题意知道，小明如果0点就到达，一定可以得到服务，故答案必然有解；

用贪心的思想，所有的情况可以分为两种：

1、小明可以在某个人到达的时间的前一秒钟到达；

2、小明在所有人办理业务完成后再到达；

于是枚举ai-1到达的时间的最小等待时间，并且再统一考虑最后一种情况即可。

时间复杂度O(N)；

思考🤔：

3.Garland

题目链接

题目大意：

小明有一群羊，羊之间用绳子连接起来，最前面的羊由小明牵着，每只羊有一个价值ai；

小明还有两个朋友，他希望和他们平分这群羊，并且三个人至少有一只羊，三个人分到的羊的总价值相同；

小明只能剪断两条绳子，问是否存在合适解？

如果不存在输出-1；

如果存在，则输出两只羊的序号，表示应该剪断牵着这两只羊的绳子；

输入数据：

第一行 数字n (3 ≤ n ≤ 1e6)

接下来n行，每行两个数字x和t；第i行的x表示第i只被第x只羊用绳子牵着（x=0表示被小明牵着），第i行的y表示第i只羊的价值；(-100<=t<=100)

Examples

input

6

2 4

0 5

4 2

2 1

1 1

4 2

output

1 4

样例解释：如图，应该剪断牵着1、4号羊的绳子，这样可以得到价值5的三个羊群。

题目解析：

抽象一下，就是把一棵树分成3部分，并且每部分的节点之和相等。

注意到题目一个很重要的条件，三个人的价值相同。

而且注意到只能减两次，那么必然有一个是子树；

于是遍历整个树，当遇到一个子树的节点和满足条件时，把这个子树从树中剔除；

再遍历整棵树，找到另外一颗子树，节点和满足条件即可。

思考🤔：

优化： 两次dfs合并成一次，当找到被剔除的节点时，return的sum=0即可。

4.Cartons of milk

题目链接

题目大意：

小红很喜欢喝牛奶，每天最多能喝k瓶牛奶；

小红有n瓶牛奶，每瓶牛奶都有一个有效时间fi，表示需要在fi天内喝完；

同时商店里有m瓶牛奶，每瓶牛奶的有效时间是gi;

小红很讨厌浪费，所以她希望能全部喝完自己的牛奶；

同时小红很喜欢牛奶，她希望尽可能喝更多的牛奶；

问小红最多能买多少瓶牛奶，保证牛奶都在保质期内喝完。

如果小红无法保证所拥有牛奶都在保质期内喝完，则输出-1；

如果小红可以保证所拥有牛奶都在保质期内喝完，则输出小红可以买的牛奶数量x；

接下来一行输出x个数字，表示小红应该买的商店牛奶序号。

输入数据：

第一行 n, m, k (1 ≤ n, m ≤ 1e6, 1 ≤ k ≤ n + m)

第二行 n个数字fi，表示小红n瓶牛奶的保质期； (0 ≤ fi ≤ 1e7)

第三行 m个数字gi，表示商店m瓶牛奶的保质期；（0 ≤ gi ≤ 1e7)

Examples

input

3 6 2

1 0 1

2 0 2 0 0 2

output

3

1 2 3

题目解析：

可以知道，小红必须是先满足喝完自己的牛奶，再尽可能去喝商店里的牛奶；

小红的策略应该是每天尽可能喝有效时间最短的牛奶，并且每天都喝k瓶；

考虑一个简单的做法：

把小红所有的牛奶排序，按照有效时间从小到大遍历每瓶牛奶，可以容易判断小红自己的牛奶是否能全部喝完；

再来考虑商店里的牛奶：假如小红能喝完数量为i+1瓶的牛奶，那么必然能喝完i瓶牛奶，具有单调性；

二分mid，表示小红能喝完mid瓶商店里的牛奶；

再使用贪心策略，从商店里选择mid瓶有效时间最长的牛奶，混入小红必须喝完的列表，然后排序；

总得复杂度O(logM_N_LogN)；

但没想到tle了，因为N=106，加上logM和logN，复杂度要加220 * 2 = 400，大概有4 * 10^8的复杂度；

于是采用优化的方案，在二分完mid之后，不与小红已有的牛奶混合排序；

用two pointers 的方法进行判断。

5. From Y to Y

题目链接

题目大意：

有一个字符数组，长度为n；（全部是小写字母）

现在有一个操作：从数组中取出两个元素s和t，把字符s和t进行合并，得到新的字符串str，然后把str放入数组；

每次操作的代价是，对于所有字母x∈{a,b,c...z}，字母x在两边s出现的次数的乘积的和；

比如说：aab+aab, 代价就是(2_2) + (1_1) = 5；

现在给出数字k，要求构造一个字符集合s，将s合并为一个字符串的最小代价刚好是k；

输入数据：

第一行，整数k (0 ≤ k ≤ 100 000)

Examples

input

12

output

abababab

样例解释：

对于字符集合 {'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'}，其中一个最小代价的方案是：

{"ab", "a", "b", "a", "b", "a", "b"}，代价是0；

{"aba", "b", "a", "b", "a", "b"}, 代价是1;

{"abab", "a", "b", "a", "b"}, 代价是1;

{"abab", "ab", "a", "b"}, 代价是0;

{"abab", "aba", "b"}, 代价是1;

{"abab", "abab"}, 代价是1;

{"abababab"}, 代价是8；

总得的最小代价是12；

题目解析：

对于代价的计算，我们看简单的例子：

aaaa的两种合并方式，

1、先(a,a)=aa, (a,a)=aa, 再(aa,aa)=aaaa；

2、先(a,a)=aa, 在(aa,a)=aaa, 再(aaa,a)=aaaa;

这两种的代价分别是1+1+4=6;

1+2+3=6;

容易知道，对于(aa,aa)的操作方式，我们可以看成是(aa,a) + (aa,a)，然后根据定义，我们可以知道(aa,a)+(a,a)=(aaa,a)；

其实合并方式1 和 合并方式2 是等价的；

再由定义，我们知道不同字母的代价计算是独立的；

对于一个字符集合s，其合并的最小代价∑x∈{a,b,c...z}, sum+=1+2+3+...+count(x-1);

这样可以得到一个快速的构造方案：

先尽可能填a，从1、2、3.... 直到不能再填，接着重复b的数量。

总结

这段时间忙完后，应该能有多余的时间，继续准备新的算法基础课程。

目前也在平衡一些职业上的选择，业余时间有限，是继续投在音视频方向，还是专注于当前的业务？

分享一些关于算法对学习和工作的帮助：在进行算法练习的时候，相当于把自己掌握的知识不断锤炼和组合出新的思路。

当我再学习新的一门技术的时候，我更倾向于先去掌握基础的知识，摸索基本的规律和原则，最后再尝试自己的一些组合与应用。期间不断优化自己对技术的积累与认知，最终通过较短的时间，可以深刻地理解技术。

而且在“爬过”华山之后，再去攀登小山峰的时候，会更加游刃有余。