红字差评系列1.第K小数
2024-10-19 12:39:30
【题目分析】
二分答案?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 ;
}
最新文章
- 【转】linux 设置用户id 设置组id
- 试图加载格式不正确的程序。 (异常来自HRESULT:0x8007000B)
- TortoiseGit安装详解
- Web信息架构——设计大型网站(第3版)(久负盛名经典再现,信息架构设计领域基石之作!)
- 【转】HTTP状态码(HTTP Status Code)
- 极简MVC的实现
- ANDROID_MARS学习笔记_S04_006_用获取access_token,access_token_secrect
- NOI2013 Day2
- 简单的方式实现javascript 小数取整
- 第19章 解释器模式(Interpreter Pattern)
- MongoDB学习笔记(三)
- 如何实现JavaScript的Map和Filter函数?
- Linux上Simplescalar/ARM的安装和运行文档
- 【阅读笔记】《C程序员 从校园到职场》第七章 指针和结构体
- cxgridchart饼状图
- properties转yml
- Spring中ApplicationContext和beanfactory区别---解析二
- RPM 方式安装 Oracle18c 的方法
- 【php】header下载文件后,文件变大的问题;(ob_clean()清空缓存)
- STL 源代码剖析 算法 stl_algo.h -- inplace_merge