51nod 1105 二分好题

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1105

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

关注

数组A和数组B，里面都有n个整数。数组C共有n^2个整数，分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1]（数组A同数组B的组合）。求数组C中第K大的数。

例如：A：1 2 3，B：2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。

Input

第1行：2个数N和K，中间用空格分隔。N为数组的长度，K对应第K大的数。(2 <= N <= 50000，1 <= K <= 10^9)

第2 - N + 1行：每行2个数，分别是A[i]和B[i]。(1 <= A[i],B[i] <= 10^9)

Output

输出第K大的数。

Input示例

Output示例

9
  好巧妙的二分套二分啊，套路啊= =
  我们可以对这个数的大小进行二分，判断一下小于等于这个mid的有多少个数，有多少个数不就说明这个数排第几吗，只要找到一个mid小于等于他的数==k就说明这是第K小的数，
题目的第K大也就是第N*N-K+1小，在统计小于等于mid的数的个数时，也要用二分，我们可以先对AB排序然后枚举每一个Ai，二分查找最多能匹配多少个Bj，累加即可。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 #define LL long long

 LL inf = (LL)1e18+;

 LL A[], B[];

 LL cal(LL K,LL N )

 {

     LL r = ;

     for (int i = ;i <= N;++i)

     {

         LL x = K / A[i];

         if (x < B[])continue;

         LL k = upper_bound(B + , B +  + N, x) - B;

         r += k - ;

     }

     return r;

 }

 int main()

 {

     LL N, K, i;

     cin >> N >> K;

     for (i = ;i <= N;++i)scanf("%lld%lld", A + i, B + i);

     sort(A + , A + N + );

     sort(B + , B +  + N);

     A[N + ] = B[N + ] = inf;

     A[] = B[] = -;

     LL l = ,r = 1e18;

     K = N*N - K + ;

     while (l < r) {

         LL mid = l + (r - l) / ;

             if (cal(mid,N) < K) l = mid + ;

             else r = mid;   //为了防止答案是mid但是有许多重复的导致cal返回值大于k，我们在这里让r=mid仍然使得mid可以被查找到，而不是被忽略

     }

     printf("%lld\n", l);

     return ;

 }

巴特西

51nod 1105 二分好题

最新文章

热门文章