第K大数-二分原来还可以这样

发布时间：2020-12-14 03:56:20 所属栏目：大数据来源：网络整理

导读：题目：数组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

题目：

数组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 示例

题目分析：

二分A[0]*B[0] -- mid-- ?A[N-1]*B[N-1],然后求出小于mid的数，用小于mid的数的个数与N*N-K+1比较，一直到最后二分跳出即为答案。

? ? ?之前一直不明白为何能够二分到准确的答案，因为如果求第3大，答案应该是8，但是7是不是也满足情况。实际上这是要看二分什么时候跳出。

?如果你发现有3个>=K的就跳出了，那么肯定不是最终答案。但是如果你到l>r的时候再跳出，二分过程中肯定有一刻指向的是序列中的某个值。

举例：还是找上面例子中第3大

k=3

l=2,r=12 mid = 7

大于=7的有3个，3>=k; 注意这个时候不能跳出而是另l=mid+1=8

l=8,r=12,mid=10

大于=10的只有1个<k，那么r=mid-1=9;

l=8，r=9,mid=8

这个同第一种情况，l=mid+1=9；

l=9,r=9,mid=9

>=9的个数2个<k，那么r=mid-1=8跳出循环（实际上跳出循环肯定是有一个所指即所求）

那么实际l=8 r=9时所指的就是答案。

代码：

//直接计算第K大

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 50002;
__int64 a[MAXN],b[MAXN];
__int64 N,K;
__int64 cnt(__int64 mid)
{
	__int64 ret = 0; 
	__int64 j = 0;
	for (__int64 i = N-1; i >= 0; -- i)
	{
		while(j<N)
		{
			if (b[j]*a[i] < mid)
				++j;
			else
				break;
		}
		ret += N-j;
	}
	return ret;
}
void binarySearch()
{
	__int64 l = a[0]*b[0];
	__int64 r = a[N-1]*b[N-1];
	__int64 ans = 0;
	while (l <= r)
	{
		__int64 mid = (l+r)>>1;
		if (cnt(mid) >= K)
		{
			ans = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout << ans << endl;
}
int main()
{
	
	while (cin >> N >> K)
	{
		//K = N*N - K + 1;
		for (int i = 0; i < N; ++ i)
		{
			cin >> a[i] >> b[i];
		}
		sort(a,a+N);
		sort(b,b+N);
		binarySearch();
	}
	return 0;
}

//计算第N*N-K+1小数，这里转换一下

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 50002;
__int64 a[MAXN],K;
__int64 cnt(__int64 mid)
{
	__int64 ret = 0; 
	__int64 j = N-1;
	for (__int64 i = 0; i < N; ++ i)
	{
		while(j>=0)
		{
			if (b[j]*a[i] > mid)
				--j;
			else
				break;
		}
		ret += j+1;
	}
	return ret;
}
void binarySearch()
{
	__int64 l = a[0]*b[0];
	__int64 r = a[N-1]*b[N-1];
	__int64 ans = 0;
	while (l <= r)
	{
		__int64 mid = (l+r)>>1;
		if (cnt(mid) >= K)
		{
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	cout << ans << endl;
}
int main()
{
	
	while (cin >> N >> K)
	{
		K = N*N - K + 1;
		for (int i = 0; i < N; ++ i)
		{
			cin >> a[i] >> b[i];
		}
		sort(a,b+N);
		binarySearch();
	}
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!