BISHI40　数组取精¶

中等通过率 50.65%python3样例通过牛客 AC

一句话

选出至多 floor(n/2)+1 个下标，使 a、b 两边都「过半」。

解题思路¶

题意复述¶

下标集合 P 被称为精华子集，当且仅当

2 * Σ_{i∈P} a_i > Σ_{i=1..n} a_i   且   2 * Σ_{i∈P} b_i > Σ_{i=1..n} b_i，

即所选下标在 A、B 两个序列上的和都严格超过各自总和的一半，同时个数满足 |P| <= floor(n/2) + 1。注意两个条件共用同一个 P：难点正在于「一组下标要同时把两个序列都顶过半」。

这题考什么¶

经典「配对贪心」构造：

把下标按 a 从大到小排序，得到 o_1, o_2, ..., o_n；
必选 o_1（a 最大的那个）；
把 o_2..o_n 两两分组 (o_2,o_3), (o_4,o_5), ...，每组选 b 更大的那个；
若 n 为偶数，o_n 落单，也一并选上。

选出的个数 = 1 + floor((n-1)/2) (+1 若 n 偶) = floor(n/2) + 1，正好卡满上限。

为什么 a 那边一定过半？把每个「未选中」的元素映射到「前一组里选中的元素」（第 1 组的未选者映射到 o_1）。由于按 a 降序排，前一组的任意元素的 a 都不小于后一组的任意元素，所以这是一个单射且每对都满足选中 >= 未选中。选中集合比未选中集合多至少一个元素（最后一组的选中者没有被映射到），而 a_i >= 1 > 0，所以 Σ选中 > Σ未选中，即 2Σ选中 > 总和。 b 那边更直接：每组里选的就是 b 大的那个，再加上白送的 o_1（b >= 1 > 0），同样严格过半。

数据规模与复杂度¶

n <= 1e5，a_i, b_i <= 1e9。排序 O(n log n)，其余 O(n)。暴力枚举子集是 2^n，完全不可行；这个贪心是本题唯一实用做法。

坑在哪¶

是严格过半（2Σ > 总和），不是 >=，所以「恰好一半」不算；
n = 1 时答案就是 {1}（floor(1/2)+1 = 1），2a_1 > a_1 成立；
n = 2 时两个都要选（o_1 与落单的 o_2），此时 2Σ = 2*总和 > 总和；
排序键必须是 a，配对内的取舍必须看 b，反过来就证不出来；
输出下标是 1-based，代码里存的是 0-based，写出去时要 +1；
答案不唯一：同时满足两条过半约束的下标集合往往有很多个，题面也明说「有多种可能的答案时输出任意一个」。样例给的是 1 4 5，本解法按「a 降序 + 组内比 b」的固定规则构造，得到的下标集合未必与样例相同。所以本地要用 special judge（特殊评测程序，按题目条件验证选手输出是否合法，而不是与标准答案逐字符比对）：本题配了 solutions/_spj/BISHI40.py，它检查下标互异且在 [1, n] 内、个数不超过 floor(n/2)+1，并真的把两个序列上的和算出来验证严格过半。

样例复核¶

n=5，A=[8,7,4,8,3]（总和 30），B=[4,2,5,3,7]（总和 21）。按 a 降序得到下标顺序 1, 4, 2, 3, 5（对应 a 值 8, 8, 7, 4, 3）；首位 1 必选；第一组 (4, 2) 里 b_4 = 3 > b_2 = 2，取 4；第二组 (3, 5) 里 b_5 = 7 > b_3 = 5，取 5。最终 P = {1, 4, 5}：a 和 19 > 15、b 和 14 > 10.5，个数 3 = floor(5/2) + 1，三条约束全部满足，与样例输出相同。

参考实现¶

solutions/BISHI40.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:n + 1]]
    b = [int(x) for x in data[n + 1:2 * n + 1]]

    order = sorted(range(n), key=lambda i: -a[i])   # 按 a 降序
    pick = [order[0]]                                # a 最大的必选
    i = 1
    while i + 1 < n:                                 # 成对处理，组内取 b 大者
        x, y = order[i], order[i + 1]
        pick.append(x if b[x] >= b[y] else y)
        i += 2
    if i < n:                                        # n 为偶数时最后一个落单
        pick.append(order[i])

    sys.stdout.write("%d\n%s\n" % (len(pick),
                                   " ".join(str(p + 1) for p in pick)))


main()

BISHI40 数组取精¶