1

1.1 题目

小美在手机上种果树，只要成熟了就可以领到免费的水果了。

小美每天可以给果树浇水，果树的成长值增加 。同时也可以给果树施肥，两次施肥至少需要间隔 2 天，果树的成长值增加 。果树成长值达到 就成熟了。

小红想知道，最少需要多少天可以领到免费的水果。

• 输入描述

一行三个整数 ，分别表示浇水、施肥、果树成熟的成长值。

• 输出描述

一行一个正数，表示最少需要多少天可以领到免费的水果。

1.2 分析

经典的蜗牛每天爬5米滑2米问题。这题没给数据范围，直接暴力模拟可以过，如果想用除法做，需要注意最后一天无法施肥，浇水则过量，不浇水则成熟值不够的情况，这种情况的答案要进一（3k+3）而不是 3k+2。

2

2.1 题目

大家一起吃饭的时候，总是小红先付钱，然后大家再把钱转给小红。

现在小红有 张账单，每张账单记录了有 个人一起吃饭，以及吃饭的消费 ，现在小红需要计算每个人需要转给小红多少钱。

由于大家都比较喜欢整数，所以大家每张账单会转给小红 ， 表示对 进行上取整。

• 输入描述

第一行输入两个整数 表示账单数和除小红外的总人数（分别用 到 表示）。
接下来 行，每 行表示一张账单。对于每张账单：
第一行输入两个整数 表示一起吃饭的人数，花费。
第二行输入 个整数，表示除小红外有哪些人一起吃饭。
数据保证， 的总和不超过 。

• 输出描述

输出 个整数，表示每个人要给小红转账的总金额。

• 示例 1

输入

2 3
3 10  
1 2  
4 8  
1 2 3

输出

6 6 2

说明 第一张账单：第 1、2 个人都会给小红转 4 元
第二张账单：第 1、2、3 个人都会给小红转 2 元
因此答案为 4+2=6，4+2=6，2

2.2 分析

题目给出 k 的规模不超过 2e5，因此直接算出分摊费用以后加到每个人的累积值上即可，时间空间复杂度都是 O(n)

3

3.1 题目

小美有两个长度为 的数组 和 。
小美想知道，能不能通过重排 数组使得对于任意 ，？
将会有 次询问。

• 输入描述

第一行一个整数 。表示询问次数。
对于每一个询问：
第一行输入两个整数 。 第二行输入 个整数 。 第二行输入 个整数 。

• 输出描述

行，每行输出一个字符串，如果能通过重排满足条件则输出"Yes"（不含引号），否则输出"No"。

• 示例 1

输入

2
5 3
-1 -2 3 4 5
-1 3 4  2 5
5 6
-1 -2 3 4 5
-1 3 4  2 5

输出

No
Yes

说明
对于第一个用例，无论怎么重排都不满足条件。 对于第一个用例，将数组 重排为 [5,3,-2,4,-1] 时满足条件。

3.2 分析

考场上没细想，直接一个升序一个降序然后相加，验证每个位置是否符合要求，时间复杂度 O(nlogn)

证明：

本题考察贪心算法。

数据规模是 500，如果暴力模拟，全排列的种数是 n!，必然超时。

本题思路代表了一类的贪心算法问题：问是否存在解，只要考虑是否存在最弱的解——“是否能从一群人里选一个人打败”等价于“是否能打败这群人里最菜的那个”。

首先，对每个 i 的限制是相同的，都是 1 到 m，因此“只对 a 排序”和“对 a 和 b 任意排序”是等价的。为简便，我们把 a,b 其中的一者降序或升序排列，然后考虑剩下的那个要如何排列。

我们来证明 a 和 b 不“反序”的可行方案一定可以优化为“反序”方案：

• 假设对排过序的两对 a,b （记为“大a, 大b, 小a, 小b”）交换，顺序和为 小a+小b, 大a+大b；“反序”和为 小a+大b, 大a+小b，两个“反序”和一定位于两个顺序和之间，从而顺序和满足范围约束时，反序和一定也满足范围约束。
• 熟悉冒泡排序的朋友可以知道，任何可行方案在 O(n^2) 次上述优化操作后，可以变为“反序”方案，从而“反序”方案就是我们要找的最弱的方案。
• 从而，直接把 a,b 数组一个升序排列一个降序排列，然后逐个比较对应位置的和是否满足要求即可，时间复杂度 O(nlogn + n) = O(nlogn)。

4

4.1 题目

给定 个正整数组成的数组，求平均数正好等于 的最长连续子数组的长度。

• 输入描述

第一行输入两个正整数 和 ，用空格隔开。
第二行输入 个正整数 ，用来表示数组。

• 输出描述

如果不存在任何一个连续子数组的平均数等于 ，则输出 -1。
否则输出平均数正好等于 的最长连续子数组的长度。

• 示例 1

输入

5 2
1 3 2 4 1

输出

3

说明
取前三个数即可，平均数为 2。

4.2 分析

其他语言的朋友可能要考虑爆 int 的问题，本 python 党笑笑不说话。

• 数据规模 200000 是 10^5 级别，简单维护前缀和再判断每个子区间的方法是 O(n^2) 的，直接 pass
• 仔细考虑以后，发现可以观察前缀和 在哪些位置之间刚好差了 距离 * k 的值。为了简便，也可以修改前缀和数组的定义，将 ai 统一减去 k，计算时使用 S[i] = S[i-1] + a[i] - k，这样问题的 k 就转化为 k=0，只需要观察“前缀和” 在哪些位置相等，然后计算对应下标的最大距离即可。
• 从而，从左到右遍历，每次把 i 加入哈希表的 S[i] 位置即可，而且这样同个位置上加入的下标是自然升序的，每次加入时更新一次 ans = max(ans, i - dic[S[i]][0]) 即可。加入时间复杂度：O(n)，空间复杂度：O(n)
  • 事实上，由上面的分析结果，当哈希表中已经有 S[i] 的结果时，可以不再把键值对 (S[i], i) 加入哈希表。