红字差评系列1.第K小数

红字差评系列1.第K小数

红字差评系列1.第K小数

红字差评系列1.第K小数

【题目分析】

  二分答案?smg,我太弱了

//不开longlong wa到挺了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn=;
ll ans=;
ll n,m,k;
ll a[maxn],b[maxn];
ll check(ll x)//找比x大的数有多少个
{
ll cnt=,p=m;
for(int i=;i<=n;i++)//枚举每一行有多少个比x小的数
{
while((ll)a[i]*b[p]>x&&p)//这里p不需要重置为m,因为ab数组sort过,某一行一定比前一行里找到的p的位置要靠前或者一样
p--;
cnt+=p;
}
return cnt;
}
int main()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%I64d%I64d%I64d",&n,&m,&k);
for(int i=;i<=n;i++)
scanf("%I64d",&a[i]);
for(int i=;i<=m;i++)
scanf("%I64d",&b[i]);
sort(a+,a+n+);
sort(b+,b+m+);
ll l=,r=a[n]*b[m];
while(l<=r)
{
ll mid=(l+r)>>;
if(check(mid)>=k)//如果比mid比实际答案要大
ans=mid,
r=mid-;
else
l=mid+;
}
cout<<ans;
fclose(stdin);fclose(stdout);
return ;
}
上一篇:亚马逊(Review、Feedback)差评怎么处理?


下一篇:php限定时间内同一ip只能访问一次