题目背景
小E还会去时空坟(shu)头(niu)去找红蓝两个神下象棋
题目描述
有一天,小E心血来潮想买个风暴皮肤。
《疯暴英雄》里卖的皮肤有N个等级,每个等级有一个稀有度ai;
《疯暴英雄》有M个英雄,每个英雄有一个稀有度bi,且每个英雄都有全部稀有度的皮肤。
我们定义一个”英雄皮肤“Gij(第i个英雄,第j等级的皮肤)的稀有度为Gij=bi*aj;
由于某种考量,小E想获得稀有度为第k小的“英雄皮肤”。
请你告诉他那个“英雄皮肤”的稀有度。
输入输出格式
输入格式:
第一行三个整数N,M和k
第二行N个整数a1到aN
第三行M个整数b1到bM
输出格式:
一个整数表示第k小的“英雄皮肤”的稀有度。
输入输出样例
输入样例#1:
5 5 18 7 2 3 5 8 3 1 3 2 5
输出样例#1:
16
说明
1≤M,N≤200000
1≤K≤M*N
1≤ai,bi≤10^9
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
二分+暴力枚举~
二分答案,枚举来计算mid在数据中的位置,然后决定向左或向右搜索。
这么暴力居然能过,实在是奇迹啊。
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long longll n,m,p,a[200001],b[200001],l,r;int main()
{freopen("number.in","r",stdin);freopen("number.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&p);for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);for(ll i=1;i<=m;i++) scanf("%lld",&b[i]);sort(a+1,a+n+1);sort(b+1,b+m+1);l=0;r=a[n]*b[m]+1;while(l+1<r){ll mid=(l+r)/2,now=m,num=0;for(ll i=1;i<=n;i++){while(now && a[i]*b[now]>=mid) now--;num+=now;}if(num>=p) r=mid;else l=mid;}printf("%lld\n",r-1);return 0;
}