(解题报告)POJ3664

报告)POJ3664"/>

(解题报告)POJ3664

两次快排
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit

Status
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 Ai votes (1 ≤ Ai ≤ 1,000,000,000) in the first round and Bi votes (1 ≤ Bi ≤ 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 Ai list; likewise, no vote count appears twice in the Bi list.

Input
* Line 1: Two space-separated integers: N and K
* Lines 2..N+1: Line i+1 contains two space-separated integers: Ai and Bi

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

解题思路：
1.这个题讲的是一群牛在投票选老大，要经过两轮，而且只有第一轮中票数排前多少个有机会进行第二轮的比较，第二轮中选出票数最多的当老大~~~
2.排序在这里主要使用c或者c++自带的排序函数qsort()与sort();[具体用法和情况请看这里！] (/)
其各自对应的头文件是
#include stdlib.h
#include algorithm
当然使用快速排序也是可以的，但不如直接使用自带函数来的方便，给出上次写快排的链接 ()
(我在这题使用的是sort函数，具体调用方法及头文件见代码！)
3.因为在本题中有三组相关联的数据，所以自然想到用结构体数组的形式来储存；
结构体的定义方式在代码中可以看到，不多赘述；
4.这个题比较坑的一个地方，也是我WA好几次的地方是一定注意牛的标号不可能是0！！！所以一定注意下标是从1开始的！

下面是具体的代码：

#include <iostream>
#include <algorithm>
#include <cstdio>     
#include <cstring>
using namespace std;    //注意头文件的使用方法，注意没有   .h!!! 
typedef struct node
{int  a;int  b;int index;
}node;int
cmp(node x,node y)
{return x.a>y.a;
}int 
cmp2(node x,node y)
{return x.b>y.b;     //注意sort函数的用法。 
}int main()
{int n,k,i;node num[50005];           while(scanf("%d%d",&n,&k)==2){memset(num,0,sizeof(num));for(i=0;i<n;i++){scanf("%d%d",&num[i].a,&num[i].b);num[i].index=i+1;  //注意牛的头数没有0！！      }sort(num,num+n,cmp);sort(num,num+k,cmp2);printf("%d\n",num[0].index);     }return 0;   
}

仅代表个人观点，不喜勿喷，欢迎交流！