题解 | Election Time-牛客假日团队赛8G题

G-Election Time_牛客假日团队赛8

https://ac.nowcoder.com/acm/contest/1069/G

题目描述

The cows are having their first election after overthrowing the tyrannical Farmer John, and Bessie is one of N cows ( $1 \leq N \leq 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 \leq K \leq 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 \leq A_i \leq 1,000,000,000$ ) in the first round and Bi votes ( $1 \leq B_i \leq 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.

输入描述:

* 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$

输出描述:

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

示例1

输入

5 3
3 10
9 2
5 6
8 4
6 5

输出

5

说明

There are 5 cows, 3 of which will advance to the second round. The cows expect to get 3, 9, 5, 8, and 6 votes, respectively, in the first round and 10, 2, 6, 4, and 5 votes, respectively, in the second.
Cows 2, 4, and 5 advance to the second round; cow 5 gets 5 votes in the second round, winning the election.

解答

这道题网上很多人都会说容易，水题之类的话，不过我看了下说这样的话的人的程序，可以说他们的程序都不及格！
为什么呢？因为他们的程序都是使用简单的二次排序水过（大概你能搜索到的多是这样的程序），那样自然可以说不及格了。
因为本题真正的目的是求前k个最大数的问题，这就需要活用快速排序。
求前k个最大数的思路：
1 选取一个数位轴，然后把大于这个数的数放到数列前面，小于这个数的数放到数列后面
2 如果前面的数的数量大于k，那么可以去掉后面的数，递归在前面的数查找前k个最大数
3 如果前面的数的数量小于k，那么截去前面的数的数量，即k减去这些数量，然后在后面数列查找
4 如果前面的数刚好等于这个k，那么就可以返回了，找到前k个大数了。
然后主要是要注意细节问题，下标没计算好，会浪费很多调试时间的。
最后AC的程序：

#include <cstdio>
#include <vector>
#include <limits.h>
using namespace std;
struct TripNums
{
	int a, b, i;
};

void seleteK(vector<TripNums> &vtri, int l, int r, int k)
{
	vector<TripNums> fro, bac;
	int val = vtri[r].a;

	for (int i = l; i < r; i++)
	{
		if (vtri[i].a < val) bac.push_back(vtri[i]);
		else fro.push_back(vtri[i]);
	}

	int i = l;
	for (int j = 0; j < (int)fro.size(); j++)
	{
		vtri[i++] = fro[j];
	}
	vtri[i++] = vtri[r];

	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);
		return ;
	}
	
	for (int j = 0; j < (int)bac.size(); j++)
	{
		vtri[i++] = bac[j];
	}
	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;
		}
		seleteK(vtri, 0, N-1, K);
		int idx, M = INT_MIN;
		for (int i = 0; i < K; i++)
		{
			if (vtri[i].b > M)
			{
				idx = vtri[i].i;
				M = vtri[i].b;
			}
		}
		printf("%d\n", idx+1);
	}
	return 0;
}

来源：靖心