题目内容


Find the Kth number

题目内容：
給定N個排序好的序列，每個序列內有M個數字。因此我們總共有N*M個數字，編號為1~N*M。
將N*M個數字排序後輸出第K個數字是多少。


Hint : 直接將N*M個數字做排序會超過時間限制。
Hint : 每次花O(N)的時間找一個數字，一直找到第K個數字也會超過時間限制。
Hint : 使用一個大小為N的heap，記錄每個序列目前最小的數字是多少，以及這是該序列的第幾個數字。
Hint : 不要將N*M個數字都產生出來，會超過memory限制。


输入格式:
只有一筆測資。
第一行有三個數字N M K，意義如題目所述。
接下來的N行，每行有2個數字a b，代表一個f(x) = ax+b。這一行的序列即為[f(1), f(2), … , f(M)]。你可以假設每一行的f(x)都會是一個遞增函數，使得你的序列肯定是排序好的序列(由小到大)。


數字範圍：
0 < N <= 17000
0 < M <= 10000


0 <= a,b <= 100


输出格式：
輸出一行數字，第K個數字是多少。


输入样例：
3 3 7
1 3
2 2
3 1


输出样例：
7

时间限制：500ms内存限制：128000kb

利用STL

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */


int main() {
	priority_queue<vector<int> > que;
	int n,m,k;
	cin>>n>>m>>k;
	int array[n][2];
	for(int i=0;i<n;i++){
		cin>>array[i][0]>>array[i][1];
	}
	// initialize que
	for(int i=0;i<n;i++)
	{
		vector<int> item;
		item.push_back(-array[i][0]-array[i][1]);
		item.push_back(i);
		item.push_back(1);
		que.push(item);
	}
	int value,idx,a,b,x,new_value;
	// k-1 times pop()
	for(int i=0;i<k-1;i++)
	{
		vector<int> item;
		item = que.top();
		que.pop();
		value = -item[0];
		idx = item[1];
		x = item[2];
		a = array[idx][0];
		b = array[idx][1];
		if(x+1<=m)
		{
			new_value=a*(x+1)+b;
			item[0]=-new_value;
			item[2]=x+1;
			que.push(item);
		}
	}
	//k-th pop
	vector<int> item;
	item = que.top();
	cout<<-item[0];
	return 0;
}