九度-1534-数组中第K小的数字[解题代码] | Acm之家
给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。
譬如A为[1,2]，B为[3,4].那么由A和B中的元素两两相加得到的数组C为[4,5,5,6]。
现在给你数组A和B，求由A和B两两相加得到的数组C中，第K小的数字。
long mid=low+((high-low)>>1);
Read full article from 九度-1534-数组中第K小的数字[解题代码] | Acm之家
给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。
譬如A为[1,2]，B为[3,4].那么由A和B中的元素两两相加得到的数组C为[4,5,5,6]。
现在给你数组A和B，求由A和B两两相加得到的数组C中，第K小的数字。
long mid=low+((high-low)>>1);
//统计小于等于 mid 的个数 |
11 | lld cntMin(lld mid){ |
12 | lld cnt = 0; |
13 | lld j = n-1; |
14 | for(int i=0; i<m; i++){ |
15 | //由于已排序，可直接利用上一次结果 |
16 | while(j >= 0 && arr1[i] + arr2[j] > mid) j--; |
17 | cnt += j+1; |
18 | } |
19 | return cnt; |
20 | } |
21 |
22 | lld low,high,mid; |
23 | int main() { |
24 | while(scanf("%lld%lld%lld", &m,&n,&k) != EOF){ |
25 | for(lld i=0; i<m; i++) scanf("%lld", &arr1[i]); |
26 | for(lld j=0; j<n; j++) scanf("%lld", &arr2[j]); |
27 | sort(arr1, arr1+m); |
28 | sort(arr2, arr2+n); |
29 | low = arr1[0] + arr2[0]; |
30 | high = arr1[m-1] + arr2[n-1]; |
31 | lld ans; |
32 | //二分逼近 |
33 | while(low <= high){ |
34 | mid = (low+high)/2; |
35 | lld cnt = cntMin(mid); |
36 | if(cnt >= k){ |
37 | ans = mid; //mid有可能是解 |
38 | high = mid-1; |
39 | }else |
40 | low = mid+1; |
41 | } |
42 | printf("%lld\n",ans); |
43 |
44 | } |
45 | return 0; |
46 | } |
