1 条题解
-
0
题目分析
数据点 1
- 暴力,挨个所有 ,sort 一遍求 大。
- 期望得分: 分。
数据点 2~5
- 贪心
- 期望得分: 分。
结论:排序后最大的 , 中必有 。
证明:设 最大,当前方案为 ,满足 ,且 。
$$\frac{x_t \times y_t + x_j \times y_j}{x_t + x_j} - \frac{x_i \times y_i + x_j \times y_j}{x_i + x_j}$$两边同时乘上
$$x_t \times y_t \times x_i + x_t \times y_t \times x_j + x_j \times y_j \times x_i + x_j \times y_j \times x_j$$$$-(x_i \times y_i \times x_t + x_i \times y_i \times x_j + x_j \times y_j \times x_t + x_j \times y_j \times x_j)$$$$= x_i \times x_t \times (y_t - y_i) + x_t \times x_j \times (y_t - y_j) + x_i \times x_j \times (y_j - y_i)$$ $$\because x_i \times x_t,x_t \times x_j,x_i \times x_j > 0$$$$\therefore \frac{x_t \times y_t + x_j \times y_j}{x_x + x_j} - \frac{x_i \times y_i + x_j \times y_j}{x_i + x_j} \ge 0$$$$\therefore \frac{x_t \times y_t + x_j \times y_j}{x_t + x_j} \ge \frac{x_i \times y_i + x_j \times y_j}{x_i + x_j}$$因此,将任意不选 的方案中, 值较小的数替换为 ,一定不劣。
所以,最优方案必定包含 。
即知复杂度为 。
综合以上算法,可以获得 分。
数据点 6~10
- 正解
- 期望得分: 分
注意到是求 大,那么求 大实际上只有两种方式:
- 通过求 大, 大, 大 …… 直到求出 大。
- 二分答案,然后数个数。
注意到 是 级别的,所以肯定选第二种了。
设当前二分的值为 ,那么我们要求的是数对 ,满足 $1 \le i < j \le n,\dfrac{x_i \times y_i + x_j \times y_j}{x_i +x_j} \ge v$ 的数量
显然,,所以变形得到
$$x_i \times y_i + x_j \times y_j \ge v \times x_i + v \times x_j$$将含 的项分别放到左边,右边,得到:
$$x_i \times y_i - v\times x_i \ge v \times x_j - x_j \times y_j$$发现两边的值都是确定的,我们分别算出。
然后就是这样一个问题了:
给出两个长度为 的序列 ,你需要求出有多少对 ,满足 。
这是一个经典问题,比较简单的一个做法是将两个序列分别排序,然后使用双指针法 数出对数。
时间复杂度为 。
- 1
信息
- ID
- 129
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者