配列中のK番目の小さい数字

配列中のK番目の小さい数字
タイトルの説明:
2つの整数配列AおよびBが与えられる.AとBの要素を2つ加算して配列Cを得ることができる.例えばAは[1,2]、Bは[3,4]である.では、AとBの要素を2つ加算して得られる配列Cは[4,5,5,6]である.今あなたに配列AとBをあげて、AとBの2つの加算から得た配列Cの中で、K番目の小さい数字を求めます.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力される第1の動作の3つの整数m,n,k(1<=m,n<=10000000,1<=k<=n*m):n,mは、入力する配列AおよびBの長さを表す.2行に続いて、配列AとBの要素を表すmとnの数があります.配列要素の範囲は[0,1 e 9]です.
出力:
各テストケースに対応して、AとBの要素の2つを加算した配列cのK番目に小さい数字が出力される.
サンプル入力:

2 2 3
1 2
3 4
3 3 4
1 2 7
3 4 5

サンプル出力:

5
6

ACコード:

#include<cstdio>
#include<algorithm>
#define MAX 100001

using namespace std;

long long A[MAX],B[MAX];

long long Count(long long aim,long long m,long long n)
{//       aim   
	long long ret,i,j;
	ret=0;
	j=n-1;
	for(i=0;i<m;i++)
	{
		while(j>=0&&A[i]+B[j]>aim)//        
			j--;         //    A[i]+B[j]<aim  A[i] B[0..j-1]  
		ret+=j+1;       //    aim，        j+1
	}
	return ret;
}

int main(int argc,char *argv[])
{
	long long m,n,k;
	long long i,j;
	long long low,mid,high,ans;
	while(scanf("%lld%lld%lld",&m,&n,&k)!=EOF)
	{
		for(i=0;i<m;i++)
			scanf("%lld",&A[i]);
		for(j=0;j<n;j++)
			scanf("%lld",&B[j]);
		sort(A,A+m);
		sort(B,B+n);
		low=A[0]+B[0];
		high=A[m-1]+B[n-1];
		ans=low;
		while(low<=high)
		{
			mid=(low+high)>>1;
			if(Count(mid,n,m)>=k)
			{
				ans=mid;
				high=mid-1;
			}
			else
				low=mid+1;
		}
		printf("%lld
",ans);
	}

	return 0;
}

問題のデータは比較的大きく,最大のKは100000*100000であり,時限は2秒であるにもかかわらず,生成前のK個の数字を直接列挙するとテストに合格できない.
では、他の方法を考えなければなりません.例えば、2点ですが、何を2点すべきか、一般的には2点で与えられたデータにある数字ですが、ここでは通用しません.
生成された数列には含まれていないが、直接答えを二分できることを考えた.
私たちは二分で近づくことができます.
二つに一つの答えX
次に生成されたシーケンスの<=Xの数を統計する.
個数>=Kの場合,これは可能な解であり,記録する.
そして私たちは小さなものに近づいた.
大きな方に近付く.
Xより小さい数字がどれだけ配列の単調性を利用できるかを計算します.
まずa,bの数字を小さいから大きいまで並べ替えます.
次にa中の要素aを列挙し,b中のどれだけの要素がaと加算されて<=Xであるかを統計する.
a<=a[i+1]では,b中の適合個数は単調に増加しない.
このような検証の複雑さはO(n+m)である.
最後の総複雑度はO(log(2*10^9)*(n+m))である.
完璧な複雑さ.