T31041:牛的选举（数据增强版）

优化，http://cs101.openjudge.cn/practice/31041/

总时间限制: 300ms 单个测试点时间限制: 210ms 内存限制: 500000kB

现在有N（1<=N<=1,000,000）头牛在选举它们的总统，选举包括两轮：第一轮投票选举出票数最多的K（1<=K<=N）头牛进入第二轮；第二轮对K头牛重新投票，票数最多的牛当选为总统。

现在给出每头牛i在第一轮期望获得的票数Ai（1<=Ai<=1,000,000,000），以及在第二轮中（假设它进入第二轮）期望获得的票数Bi（1<=Bi<=1,000,000,000），请你预测一下哪头牛将当选总统。幸运的是，每轮投票都不会出现票数相同的情况。

输入

第1行：N和K 第2至N+1行：第i+1行包括两个数字：Ai和Bi

输出

当选总统的牛的编号（牛的编号从1开始）

样例输入

样例输出

提示

1、n较大，算法复杂度不应该超过O(n) 2、知识点：快速排序 3、用sys.stdin.read()减少数据I/O时间

来源：xzm

为了应对单点 210ms 的极严苛时间限制，需要将 Python 的运行效率提升到极致。

在上一版代码中，主要的瓶颈在于创建了 1,000,000 个元组对象以及在排序时调用了 Python 层面的 key 函数。这些操作在大数据量下会产生极高的对象分配和垃圾回收开销。

极致优化方案

使用 bytes 读取：使用 sys.stdin.buffer.read() 以字节流形式读取，比普通字符串读取更快。
完全避免元组创建：不创建任何结构体或元组，直接利用原数组的索引。
消除 Lambda 表达式：利用 Python 列表的内置 C 级方法 __getitem__ 作为 sort 和 max 的 key。由于无需调用 Python 虚拟机的函数栈，运行速度会大幅提升。
小 $K$ 堆优化：当 $K$ 较小时，使用 heapq.nlargest 代替全量排序。
禁用垃圾回收 (GC)：在程序执行前通过 gc.disable() 暂时关闭垃圾回收，避免在大规模对象销毁时产生停顿。

python

import gc
import heapq
import sys


def solve():
    # 暂时禁用垃圾回收以提升执行速度
    gc.disable()

    # 以字节流形式读取输入，速度最快
    input_bytes = sys.stdin.buffer.read().split()
    if not input_bytes:
        return

    # 快速转换为整型列表
    data = list(map(int, input_bytes))
    N = data[0]
    K = data[1]

    # 利用高速 C 切片分离 A 轮和 B 轮数据
    As = data[2::2]
    Bs = data[3::2]

    # 第一轮筛选：找出 As 中值最大的前 K 个索引
    # 使用内置的 As.__getitem__ 替代 lambda 表达式，速度极快
    if K < 1000:
        top_k = heapq.nlargest(K, range(N), key=As.__getitem__)
    else:
        top_k = sorted(range(N), key=As.__getitem__, reverse=True)[:K]

    # 第二轮筛选：在 top_k 索引中，找出使 Bs 值最大的索引
    winner_idx = max(top_k, key=Bs.__getitem__)

    # 输出 1 基准的牛编号
    print(winner_idx + 1)


if __name__ == "__main__":
    solve()

T31041:牛的选举（数据增强版） ​

T31041:牛的选举（数据增强版）