基准时间限制：1 秒 空间限制：131072 KB 分值: 40
收藏 
关注 数组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示例
3 21 22 33 4
Output示例
9
之前做过的left right都是数组的下标，找数组中的元素。这次是直接给那个数的范围，找数组中的数。
双二分。一开始我是想第k大的数，即是 第n*n-k+1小的数，所以找小的元素，结果前19组test都过了，就第20组一直WA。后来想N最大50000，N*N超过了long long了。这个思路只能被划掉。乖乖找第k大的，记录有多少比mid大的，再去比较。
代码：
#include#include #include #include #include #include #pragma warning(disable:4996)using namespace std;long long a[50005], b[50005];int len, k;int search(long long y, long long x){ int i, left = 1, right = len; long long mid, ans=len; while (left <= right) { mid = left + (right - left) / 2; if (a[y] * b[mid] >= x) { ans = min(ans, mid); right = mid - 1; } else { left = mid + 1; } } return ans;}bool check(long long x){ int i, ans = 0; for (i = 1; i <= len; i++) { if (a[i] * b[len] < x)continue; ans += ((len- search(i, x))+1); } return ans >= k;}int main(){ int i; long long start, end, mid, ans; cin >> len >> k; for (i = 1; i <= len; i++) cin >> a[i] >> b[i]; sort(a + 1, a + len + 1); sort(b + 1, b + len + 1); start = a[1] * b[1] - 1; end = a[len] * b[len] + 1; ans = 0; while (end - start > 1) { mid = start + (end - start) / 2; if (check(mid)) { ans = max(ans, mid); start = mid; } else { end = mid; } } cout << ans << endl; return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。