51nod 1105：第K大的数

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

关注

数组A和数组B，里面都有n个整数。数组C共有n^2个整数，分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1]（数组A同数组B的组合）。求数组C中第K大的数。

例如：A：1 2 3，B：2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。

Input

第1行：2个数N和K，中间用空格分隔。N为数组的长度，K对应第K大的数。(2 <= N <= 50000，1 <= K <= 10^9)
第2 - N + 1行：每行2个数，分别是A[i]和B[i]。(1 <= A[i],B[i] <= 10^9)

Output

输出第K大的数。

Input示例

Output示例

之前做过的left right都是数组的下标，找数组中的元素。这次是直接给那个数的范围，找数组中的数。

双二分。一开始我是想第k大的数，即是第n*n-k+1小的数，所以找小的元素，结果前19组test都过了，就第20组一直WA。后来想N最大50000，N*N超过了long long了。这个思路只能被划掉。乖乖找第k大的，记录有多少比mid大的，再去比较。

代码：

<pre name="code" class="cpp">#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

long long a[50005], b[50005];
int len, k;

int search(long long y, long long x)
{
	int i, left = 1, right = len;
	long long mid, ans=len;
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (a[y] * b[mid] >= x)
		{
			ans = min(ans, mid);
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return ans;
}

bool check(long long x)
{
	int i, ans = 0;
	for (i = 1; i <= len; i++)
	{
		if (a[i] * b[len] < x)continue;
		ans += ((len- search(i, x))+1);
	}
	return ans >= k;
}

int main()
{
	int i;
	long long start, end, mid, ans;
	cin >> len >> k;
	for (i = 1; i <= len; i++)
		cin >> a[i] >> b[i];
	
	sort(a + 1, a + len + 1);
	sort(b + 1, b + len + 1);

	start = a[1] * b[1] - 1;
	end = a[len] * b[len] + 1;
	ans = 0;

	while (end - start > 1)
	{
		mid = start + (end - start) / 2;
		if (check(mid))
		{
			ans = max(ans, mid);
			start = mid;
		}
		else
		{
			end = mid;
		}
	}
	cout << ans << endl;

	return 0;
}