[基本練習]USACO Jan08 奶牛的選舉 elect

題目描述
在推翻了Farmer John這個殘暴的統治者後，奶牛們舉行了她們的第一次總統大選，貝茜也是N(1 <= N <= 50,000)頭候選奶牛之一。不過，作爲一頭有遠見的奶牛，貝茜想在選舉開始前就計算出，哪頭奶牛最有可能在競爭中勝出。

選舉分兩輪進行。第一輪中，得票最多的K(1 <= K <= N)頭奶牛晉級到下一輪，在第二輪選舉中得票最多的奶牛成爲最終的總統。

現在，貝茜告訴了你奶牛i在第一輪投票中的期望得票數A_i(1 <= A_i <= 1,000,000,000)以及她在第二輪投票中的期望得票數B_i(1 <= B_i <= 1,000,000,000)（如果奶牛i能成功晉級的話），她希望你幫她計算一下，如果這些數據無誤，那麼哪頭奶牛將成爲總統。任何數值都不會在A_i 列表中出現兩次，在B_i列表中也是如此。

程序名: elect

輸入格式:

第1行: 2個用空格隔開的整數：N 和 K

第2..N+1行: 第i+1爲2個用空格隔開的整數：A_i 和 B_i

輸入樣例 (elect.in):

5 3

3 10

9 2

5 6

8 4

6 5

輸入說明:

一共有5頭奶牛參加選舉，在第一輪中得票最多的3頭奶牛可以晉級至第二輪。奶牛們在第一輪中的得票期望分別爲3，9，5，8，6，第二輪中，分別爲10，2，6，4，5。

輸出格式:

第1行: 輸出1個整數，爲將被選爲總統的奶牛的編號

輸出樣例 (elect.out):

5

輸出說明:

奶牛2，4，5晉級到第二輪。奶牛5在第二輪投票中得到了最多的5票，贏得了選舉的最終勝利。

【分析】

通過分析發現，這就是一個簡單的排序問題，通過兩次快速排序即可解決問題。

可以用一個結構來儲存某一奶牛的編號、第一輪得票數、第二輪得票數，先對第一輪得票數調用快速排序函數，再對第二輪得票數調用快速排序函數，最後輸出排在數組第一位的奶牛的編號即可。

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef unsigned int usint;

class COW
{
public:
    usint Fir;
    usint Sec;
    usint num;
}C[50001];

int N,K;

int cmp(const void *a,const void *b)
{
    class COW *c=(class COW *)a;
    class COW *d=(class COW *)b;
    return d->Fir-c->Fir;
}

int Cmp(const void *a,const void *b)
{
    class COW *c=(class COW *)a;
    class COW *d=(class COW *)b;
    return d->Sec-c->Sec;
}

void init()
{
    scanf("%d %d\n",&N,&K);
    for (int i=1;i<=N;i++)
    {
        C[i].num=i;
        scanf("%d %d\n",&C[i].Fir,&C[i].Sec);
    }
    qsort(C+1,N,sizeof(C[0]),cmp);
    qsort(C+1,K,sizeof(C[0]),Cmp);
    return;
}

void print()
{
    for (int i=1;i<=N;i++)
        printf("%d %d %d\n",C[i].num,C[i].Fir,C[i].Sec);
}

int main()
{
    freopen("elect.in","r",stdin);
    freopen("elect.out","w",stdout);
    init();
    //print();
    cout<<C[1].num<<endl;
    return 0;
}