九度 1534 数组中第K小的数字
【摘要】 题目链接~~>
做题感悟:这题竟然用二分真心没想到,看来不管什么算法只要会用都很强大。
解题思路:先确定两两合并后最小值和最大值,min= a[0]+b[0] ,max=a[n-1]+b[m-1] 这很明显,然后再min~max中二分枚举值,然后查看枚举的这个值是否是第 k 大。
代码:
#include<stdio.h>#include<io...
做题感悟:这题竟然用二分真心没想到,看来不管什么算法只要会用都很强大。
解题思路:先确定两两合并后最小值和最大值,min= a[0]+b[0] ,max=a[n-1]+b[m-1] 这很明显,然后再min~max中二分枚举值,然后查看枚举的这个值是否是第 k 大。
代码:
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<stack>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
#define LEN sizeof(struct node)
-
#define lld long long int
-
const double PI = 3.1415926 ;
-
const double INF = 99999999 ;
-
const int MX =1000005 ;
-
lld n,m,k ;
-
lld a[MX],b[MX] ;
-
lld binary_search(lld mid) // 判断该值第几小
-
{
-
lld cnt=0 ;
-
for(int i=0 ;i<n ;i++)
-
{
-
if(mid<a[i]) break ;
-
lld x=mid-a[i] ;
-
cnt+=upper_bound(b,b+m,x)-b ;
-
}
-
return cnt ;
-
}
-
int main()
-
{
-
while(~scanf("%lld%lld%lld",&n,&m,&k))
-
{
-
for(int i=0 ;i<n ;i++)
-
scanf("%lld",&a[i]) ;
-
for(int i=0 ;i<m ;i++)
-
scanf("%lld",&b[i]) ;
-
sort(a,a+n) ; // 排序
-
sort(b,b+m) ;
-
-
lld le=a[0]+b[0],rt=a[n-1]+b[m-1] ;
-
lld mid ;
-
while(le+1<rt) // 二分查找第k小
-
{
-
mid=(rt+le)/2 ;
-
if(binary_search(mid)>=k)
-
rt=mid ;
-
else le=mid ;
-
}
-
printf("%lld\n",rt) ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/21865243
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)