cugb 1220 두 배열 곱 하기 k 대수-2 점-2

http://acm.cugb.edu.cn/JudgeOnline/showproblem?problem_id=1220 
 
 
제목:두 개의 배열 a 와 b 요소 의 개 수 는 모두 n(10000)개 이 고 모두 정수 이다.a[]*b[]가 생 성 한 c[]배열 의 k 번 째 대 수 를 구하 십시오.
 
 
분석:2 분 에 하나의 값 v 를 구하 고 이 값 은 마지막 c 의 요소 중>=v 의 개수>=k 입 니 다.그리고 a 배열 을 스 캔 하고 2 분 b 배열 은>=v 의 요소 개 수 를 얻 습 니 다.
사실 2 분 b 수 조 는 생략 할 수 있 습 니 다.a 와 b 배열 이 모두 정렬 되 어 있 기 때문에 a 중의 요 소 를 뒤로 쓸 면 b 중의 요 소 를 뒤로 쓸 면 결 과 를 얻 을 수 있 습 니 다.
 
2 점 은 죽 여 버 릴 거 야...
 
 
코드:
하나,둘.100+ms。。오 랜 만 에 랭 킹 1 이 네.

#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

const int N=10010;
int n, k, a[N], b[N], flag;

int cal(int num)
{
	int i, j, k, ans, tmp;
	if(a[n-1]*b[n-1]<=num)
		return 0;
	j = n-1;
	ans = 0;
	for(i=0; i<n; i++)
	{
		for(; j>=0 && a[i]*b[j]>num; j--);
		ans += n-1-j;
	}
	return ans;
}

int bs() 
{
	int i, l, r, mid, ans, tmp;
	l=1, r=a[n-1]*b[n-1];
	while(l<=r)
	{
		flag = 0;
		mid = (l+r)>>1;
		tmp = cal(mid);
		if(tmp>=k)
			l = mid+1;
		else
			r = mid-1;
	}
	//r        r    >=k  ，  r+1    。。。
	return r+1;
}

int main()
{
	int i, j, cas;
	scanf("%d", &cas);
	while(cas--)
	{
		scanf("%d%d", &n, &k);
		for(i=0; i<n; i++)
			scanf("%d", &a[i]);
		for(i=0; i<n; i++)
			scanf("%d", &b[i]);
		sort(a, a+n);
		sort(b, b+n);
		printf("%d
", bs());
	}

	return 0;
}

 
 
2 점.300+ms

#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

const int N=10010;
int n, k, a[N], b[N], flag;

int bs1(int i, int num) //   a[i]  >num    
{
	int l, r, mid;
	l=0, r=n-1;
	while(l<=r)
	{
		mid = (l+r)>>1;
		if(a[i]*b[mid]<=num)
			l = mid+1;
		else
			r = mid-1;
	}
	//r   <=num       
	return n-1-r; //  >num    
}

int bs() 
{
	int i, l, r, mid, ans, tmp;
	l=1, r=a[n-1]*b[n-1];
	while(l<=r)
	{
		flag = 0;
		mid = (l+r)>>1;
		tmp = 0;
		for(i=0; i<n; i++) // a  ，  b
			tmp += bs1(i, mid);
		if(tmp>=k)
			l = mid+1;
		else
			r = mid-1;
	}
	//r        r    >=k  ，  r+1    。。。
	return r+1;
}

int main()
{
	int i, j, cas;
	scanf("%d", &cas);
	while(cas--)
	{
		scanf("%d%d", &n, &k);
		for(i=0; i<n; i++)
			scanf("%d", &a[i]);
		for(i=0; i<n; i++)
			scanf("%d", &b[i]);
		sort(a, a+n);
		sort(b, b+n);
		printf("%d
", bs());
	}

	return 0;
}