1 条题解

  • 0
    @ 2026-11-15 16:32:57

    题目分析

    数据点 1

    • 暴力,挨个所有 f(i,j)f(i,j),sort 一遍求 kk 大。
    • 期望得分:1010 分。

    数据点 2~5

    • 贪心
    • 期望得分:4040 分。

    结论:排序后最大的 f(i,j)f(i,j),yi,yjy_i,y_j 中必有 max⁡1≤i≤n{yi}\max_{1\le i\le n}\{y_i\}。

    证明:设 yty_t 最大,当前方案为 (i,j)(i,j),满足 i≠t,j≠ti \neq t,j \neq t,且 yj≥yiy_j \ge y_i。

    $$\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}$$

    两边同时乘上 (xt+xj)×(xi+xj)(x_t + x_j) \times (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)$$∵yx≥yj≥yi\because y_x \ge y_j \ge y_i ∴yt−yi,yt−yj,yj−yi≥0\therefore y_t - y_i,y_t - y_j,y_j - y_i \ge 0 $$\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}$$

    因此,将任意不选 tt 的方案中,yy 值较小的数替换为 tt,一定不劣。

    所以,最优方案必定包含 tt。

    即知复杂度为 O(n)O(n)。

    综合以上算法,可以获得 5050 分。

    数据点 6~10

    • 正解
    • 期望得分:100100 分

    注意到是求 kk 大,那么求 kk 大实际上只有两种方式:

    1. 通过求 11 大,22 大,33 大 …… 直到求出 kk 大。
    2. 二分答案,然后数个数。

    注意到 kk 是 101010^{10} 级别的,所以肯定选第二种了。

    设当前二分的值为 vv,那么我们要求的是数对 (i,j)(i,j),满足 $1 \le i < j \le n,\dfrac{x_i \times y_i + x_j \times y_j}{x_i +x_j} \ge v$ 的数量

    显然,xi+xj>0x_i+x_j>0,所以变形得到

    $$x_i \times y_i + x_j \times y_j \ge v \times x_i + v \times x_j$$

    将含 i,ji,j 的项分别放到左边,右边,得到:

    $$x_i \times y_i - v\times x_i \ge v \times x_j - x_j \times y_j$$

    发现两边的值都是确定的,我们分别算出。

    然后就是这样一个问题了:

    给出两个长度为 nn 的序列 {an},{bn}\{a_n\},\{b_n\},你需要求出有多少对 (i,j)(i,j),满足 ai≥bja_i \ge b_j。

    这是一个经典问题,比较简单的一个做法是将两个序列分别排序,然后使用双指针法 O(n)O(n) 数出对数。

    时间复杂度为 O(nlog⁡vlog⁡n)O(n\log v\log n)。

    • 1

    信息

    ID
    129
    时间
    2000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者