POJ 3664 Election Time 題解

這道題網上很多人都會說容易，水題之類的話，不過我看了下說這樣的話的人的程序，可以說他們的程序都不及格！

為什麼呢？因為他們的程序都是使用簡單的二次排序水過（大概你能搜索到的多是這樣的程序），那樣自然可以說不及格了。

因為本題真正的目的是求前k個最大數的問題，這就需要活用快速排序。

求前k個最大數的思路：

1 選取一個數位軸，然後把大於這個數的數放到數列前面，小於這個數的數放到數列後面

2 如果前面的數的數量大於k，那麼可以去掉後面的數，遞歸在前面的數查找前k個最大數

3 如果前面的數的數量小於k，那麼截去前面的數的數量，即k減去這些數量，然後在後面數列查找

4 如果前面的數剛好等於這個k，那麼就可以返回了，找到前k個大數了。

然後主要是要注意細節問題，下標沒計算好，會浪費很多調試時間的。

最後AC的程序：

#include 
#include 
#include 
using namespace std;
struct TripNums
{
	int a, b, i;
};

void seleteK(vector &vtri, int l, int r, int k)
{
	vector 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 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
, idx+1);
	}
	return 0;
}