POJ 3664 Election Time(简单的快速排序)

Election Time

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5420		Accepted: 2944

Description

The cows are having their first election after overthrowing the tyrannical Farmer John, and Bessie is one of N cows (1 ≤ N ≤ 50,000) running for President. Before the election actually happens, however, Bessie wants to determine who has the best chance of winning.

The election consists of two rounds. In the first round, the K cows (1 ≤ K ≤ N) cows with the most votes advance to the second round. In the second round, the cow with the most votes becomes President.

Given that cow i expects to get A_i votes (1 ≤ A_i ≤ 1,000,000,000) in the first round and B_i votes (1 ≤ B_i ≤ 1,000,000,000) in the second round (if he or she makes it), determine which cow is expected to win the election. Happily for you, no vote count appears twice in the A_i list; likewise, no vote count appears twice in the B_i list.

Input

* Line 1: Two space-separated integers: N and K 
* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i and B_i

Output

* Line 1: The index of the cow that is expected to win the election.

Sample Input

5 3

3 10

9 2

5 6

8 4

6 5

Sample Output

5

Source

USACO 2008 January Bronze

 解题报告：题意就是牛的淘汰赛，规则有两轮，再第一轮中选出前k个牛，再在这k只牛中选取第二轮中票数最多的牛，输出它的编号，进行两次排序就行！

代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int MAX = 50010;
int n, k;
struct node
{
    int a;
    int b;
    int num;
}cow[MAX];
int cmpa(node p, node q)//先按a从大到小排序，若a相等则按b从大到小排序
{
    if (p.a == q.a) return p.b > q.b;
    return p.a > q.a;
}
int cmpb(node p, node q)//先按b从大到小排序，若b相等则按a从大到小排序
{
    if (p.b == q.b) return p.a > q.a;
    return p.b > q.b;
}
int main()
{
    int i;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        for (i = 0; i < n; ++i)
        {
            scanf("%d%d", &cow[i].a, &cow[i].b);
            cow[i].num = i + 1;//牛的标号
        }
        sort(cow, cow + n, cmpa);//前n个牛排序
        sort(cow, cow + k, cmpb);//前k个牛排序
        printf("%d\n", cow[0].num);
    }
    return 0;
}