基準時間限制：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示例
3?2 1?2 2?3 3?4
Output示例
9
二分?
A,B數組分別排序
左端點為A[1]*B[1] 右端點A[n]*B[n]
找比mid小的數有多少個?
若滿足條件 更新答案?
屠龍寶刀點擊就送
#include <algorithm> #include <cstdio> typedef long long LL; using namespace std; LL cnt=0,n,k,A[50050],B[50050];LL check(LL now) {LL ans=0;for(LL i=1;i<=n;i++){LL l=1,r=n,num=0;while(l<=r){LL mid=(l+r)>>1;if(A[i]*B[mid]<now) num=mid,l=mid+1;else r=mid-1;}ans+=num;}return ans<k?1:0; } int main() {scanf("%lld%lld",&n,&k);k=(n*n)-k+1;for(LL i=1;i<=n;i++)scanf("%lld%lld",&A[i],&B[i]);sort(A+1,A+1+n);sort(B+1,B+1+n);LL mid,ans;LL l=A[1]*B[1],r=A[n]*B[n];while(l<=r){mid=(l+r)>>1;if(check(mid)) ans=mid,l=mid+1;else r=mid-1;}printf("%lld",ans);return 0; }
?
