题解：Election Time（P3664）

一、题目分析

本题要求模拟奶牛选举过程，确定最终获胜的奶牛。关键规则：

1. 第一轮选举：选出票数前K的奶牛进入第二轮
2. 第二轮选举：进入第二轮的奶牛中，票数最多的当选
3. 输入保证第一轮和第二轮票数均唯一，需输出当选奶牛的编号（从1开始）

二、解题思路

1. 问题拆解：

   • 第一步：从N头奶牛中选出第一轮票数前K的奶牛
   • 第二步：在这K头奶牛中找出第二轮票数最多的

2. 算法选择：

   • 第一轮筛选：使用快速选择算法（QuickSelect），时间复杂度O(N)
   • 第二轮选举：遍历K头奶牛，找出最大第二轮票数

三、代码解析

#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

struct TripNums {
    int a, b, i;  // a:第一轮票数，b:第二轮票数，i:原始编号
};

// 快速选择算法：筛选出前K个a最大的元素
void seleteK(vector<TripNums>& vtri, int l, int r, int k) {
    vector<TripNums> fro, bac;
    int val = vtri[r].a;  // 以最后一个元素的a值为基准
    
    // 分区：a≥val的放入fro，a<val的放入bac
    for (int i = l; i < r; i++) {
        if (vtri[i].a < val)
            bac.push_back(vtri[i]);
        else
            fro.push_back(vtri[i]);
    }
    
    // 重构数组：fro + 基准元素 + bac
    int i = l;
    for (int j = 0; j < (int)fro.size(); j++)
        vtri[i++] = fro[j];
    vtri[i++] = vtri[r];
    
    // 判断基准位置是否为第K大元素
    if ((int)fro.size() == k || (int)fro.size() + 1 == k)
        return;
    
    // 递归处理左半区或右半区
    if ((int)fro.size() > k)
        seleteK(vtri, l, l + (int)fro.size() - 1, k);
    else
        seleteK(vtri, l + (int)fro.size() + 1, r, k - (int)fro.size() - 1);
}

int main() {
    int N, K;
    while (~scanf("%d %d", &N, &K)) {
        vector<TripNums> vtri(N);
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &vtri[i].a, &vtri[i].b);
            vtri[i].i = i;  // 记录原始编号（从0开始）
        }
        
        // 筛选出第一轮票数前K的奶牛
        seleteK(vtri, 0, N - 1, K);
        
        // 在第二轮中找票数最多的奶牛
        int idx = 0, M = INT_MIN;
        for (int i = 0; i < K; i++) {
            if (vtri[i].b > M) {
                M = vtri[i].b;
                idx = vtri[i].i;
            }
        }
        
        printf("%d\n", idx + 1);  // 编号从1开始输出
    }
    return 0;
}

四、关键步骤解析

1. 数据结构设计
   $TripNums$结构体存储每头奶牛的：

   • 第一轮票数$a$
   • 第二轮票数$b$
   • 原始编号$i$（从0开始，输出时+1）

2. 快速选择算法

   • 以基准元素$vtri[r].a$为界，将数组分为$a≥val$和$a<val$两部分
   • 若$a≥val$的元素数≥K，递归左半区
   • 否则递归右半区，继续筛选剩余需要的元素数
   • 时间复杂度平均O(N)，最坏O(N²)，但实际表现良好

3. 第二轮选举
   遍历前K头奶牛，找出$b$最大的奶牛，输出其编号（注意+1转换为1-based）

五、示例解析

输入：

5 3
3 10  --> 奶牛1
9 2   --> 奶牛2
5 6   --> 奶牛3
8 4   --> 奶牛4
6 5   --> 奶牛5

1. 第一轮筛选：
   第一轮票数$a$为[3,9,5,8,6]，前3大的$a$是9,8,6，对应奶牛2、4、5进入第二轮。

2. 第二轮选举：
   第二轮票数$b$为2,4,5，最大的$b=5$对应奶牛5，输出编号5。

六、注意事项

1. 快速选择的正确性

   • 算法筛选的是前K个$a$最大的元素，而非严格排序
   • 由于题目保证$a$唯一，无需处理相等情况

2. 编号转换
   输入的奶牛编号从1开始，但代码中存储为0-based，输出时需+1。

3. 数据范围
   N≤50000，快速选择的递归深度需注意栈溢出风险（可改用非递归实现）

七、复杂度分析

• 时间复杂度：
  快速选择平均O(N)，最坏O(N²)；第二轮遍历O(K)，总复杂度平均O(N)。
• 空间复杂度：O(N)，存储奶牛信息和分区临时数组。

八、优化方向

1. 快速排序替代
   若N较小（如N≤1000），直接排序前K个元素更简单，时间复杂度O(N log N)。

2. 非递归快速选择
   避免递归栈溢出，适合N较大的情况。