Dave的组合数组
Time Limit: C/C++ 1 s Java/Python 3 s Memory Limit: 128 MB Accepted: 3 Submit: 14
Submit My Status
Problem Description
数组 AA 和数组 BB ，里面都有 nn 个整数。
数组 CC 共有 n2n2 个整数，分别是：
A[0]∗B[0],A[0]∗B[1]......A[0]∗B[n−1]A[0]∗B[0],A[0]∗B[1]......A[0]∗B[n−1]
A[1]∗B[0],A[1]∗B[1]......A[1]∗B[n−1]A[1]∗B[0],A[1]∗B[1]......A[1]∗B[n−1]
............
A[n−1]∗B[0],A[n−1]∗B[1]......A[n−1]∗B[n−1]A[n−1]∗B[0],A[n−1]∗B[1]......A[n−1]∗B[n−1]
是数组 AA 同数组 BB 的组合,求数组 CC 中第 KK 大的数。
例如：
A：123，B：234A：123，B：234。
AA与BB组合成的CC为
A[0]A[0] A[1]A[1] A[2]A[2]
B[0]B[0] 22 33 44
B[1]B[1] 44 66 88
B[2]B[2] 66 99 1212
共9个数。
Input
第1行：22个数NN和KK，中间用空格分隔。NN为数组的长度，KK对应第KK大的数。(2≤N≤50000，1≤K≤109)(2≤N≤50000，1≤K≤109)
第−N+1−N+1行：每行2个数，分别是A[i]和B[i]。(1≤A[i],B[i]≤109)(1≤A[i],B[i]≤109)
Output
输出第K大的数。
Sample Input
3 2
1 2
2 3
3 4
Sample Output
9
分析：对A数列和B数列进行排序，然后二分法找出第k大
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll a[50005],b[50005];
int n;
ll cmd(int x,int y)
{
return x>y;
}
int num(ll mid)
{
int j=1;
//int j=n;
ll ans=0;
for(int i=1;i<=n;i++)
{
while(a[i]*b[j]>mid)//因为a从大到小排序，所以后面的a匹配的个数在前面a匹配个数的基础上加
j++;
ans+=j-1;//当前所有i匹配到的j的个数
// while(j>=0&&a[i]*b[j]>mid)
// j--;
// ans+=n-j;
}
return ans+1;//比它大的有ans个，它是第ans+1大
}
int main()
{
int k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i],&b[i]);
sort(a+1,a+n+1);//从小到大
sort(b+1,b+n+1,cmd);//从大到小
ll x=a[1]*b[n];//最小
ll y=a[n]*b[1];//最大
//sort(b+1,b+n+1);
// ll x=a[1]*b[1];
// ll y=b[n]*a[n];
while(x!=y)
{
ll mid=x+y>>1;
int kk=num(mid);//找mid是第几大
if(kk<=k)//mid排名比k前,mid在第k大后面
y=mid;
else
x=mid+1;
}
printf("%lld\n",x);
return 0;
}