ACM_求第k大元素(两次二分)
2024-09-03 01:50:05
求第k大
Time Limit: 6000/3000ms (Java/Others)
Problem Description:
给定两个数组A和B,大小为N,M,每次从两个数组各取一个数相乘放入数组C,最终得到一个N*M的数组C。求C中第K大的数。
Input:
输入包含多组测试数据,每组数据首先输入两个整数N,M,K,接下来一行有N个整数Ai,再接下来一行有M个整数Bi。(1≤N,M≤10^5,1≤Ai,Bi≤10^5,1≤K≤N*M)
Output:
对于每组数据,输出答案。
Sample Input:
3 2 2
1 2 3
1 2 2 2 1
1 1
1 1
Sample Output:
4
1
解题思路:由于数据非常大,因此考虑二分来做:先对两个数组降序排,然后外层二分查找第k大元素,内层二分查找当前mid在数组C中排第几并作为外层二分查找的条件,最终的答案就是l-1,详解看代码。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+;
int n,m;LL k,l,r,mid,ans,A[maxn],B[maxn];
inline LL read(){
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void print(LL x){
if(x<)putchar('-'),x=-x;
if(x>)print(x/);
putchar(x%+'');
}
bool check(LL mid){
LL cnt=;
for(int i=;i<n;++i){
int lt=,rt=m-;
while(lt<=rt){///二分找b数组中某个元素与当前A[i]乘积不小于mid的最大下标lt-1
int midt=(lt+rt)>>;
if(A[i]*B[midt]>=mid)lt=midt+;///说明可能还有更小的元素与A[i]相乘之后不小于mid,则往右边找
else rt=midt-;///否则往左边找
}
cnt+=lt;///退出条件是rt=lt-1,而下标是0开始的,所以lt不用减1,累加当前满足条件的个数
}
return cnt>=k;
}
int main(){///时间复杂度为log2(nm)*n*log2(m)
while(~scanf("%d%d%lld",&n,&m,&k)){
for(int i=;i<n;++i)A[i]=read();
for(int i=;i<m;++i)B[i]=read();
sort(A,A+n,greater<LL>());///降序排
sort(B,B+m,greater<LL>());
l=A[n-]*B[m-],r=A[]*B[];
while(l<=r){///二分找第k大元素(即两个数的乘积)
mid=(l+r)>>;
if(check(mid))l=mid+;///说明mid可以更大,继续往右边找
else r=mid-;///否则往左边找
}
print(l-);puts("");
}
return ;
}
最新文章
- javascriptone
- node.js报错总结
- Xcode各版本官方下载, Mac和IOS及Xcode版本历史
- mysql 出现错误Incorrect file format
- 最短路(Bellman_Ford) POJ 1860 Currency Exchange
- dedecms后台上传图片附件返回302的问题
- VS2012编译出来的程序,在XP上运行,出现“.exe 不是有效的 win32 应用程序” “not a valid win32 application”
- Web scraping with Python (part II) « Jean, aka Sig(gg)
- 高性能管线式HTTP请求(实践&#183;原理&#183;实现)
- SVN版本库修改URL路径或者IP地址
- 【Android】带进度条的WebView
- AOP及专有名词通俗解答
- 浏览器控制台调试json数据
- 视音频编解码学习工程:H.264分析器
- Java_循环
- 洛谷.5284.[十二省联考2019]字符串问题(后缀自动机 拓扑 DP)
- SecureRandom
- Linux 操作 oracle 数据库
- stark组件之路由分发【模仿Django的admin】
- sql中计算某天是全年的第几周及取得某天的所在周的周一的日期的函数
热门文章
- A new session could not be created. (Original error: Requested a new session but one was in progress) )错误解决办法
- java 调用ant的自己定义task,默认不是build.xml 的一点问题
- word2vec学习 spark版
- dp求顺序hdu1160
- 2016/06/13 phpexcel 未完待续
- REST RPC HTTP vs 高性能二进制协议 序列化和通信协议
- 端口扫描 开启 防火墙 iptables SELinux
- Hadoop集群搭建-虚拟机安装(转)(一)
- HDU 2746 Cyclic Nacklace
- 利用JS判断当前来路域名并跳转到指定页面