九度 1534 数组中第K小的数字

本文主要是介绍九度 1534 数组中第K小的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接~~>

做题感悟：这题竟然用二分真心没想到，看来不管什么算法只要会用都很强大。

解题思路：先确定两两合并后最小值和最大值，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 ;
}

 

这篇关于九度 1534 数组中第K小的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---