2013
12-13

九度-1534-数组中第K小的数字[解题代码]

2 2 3
1 2
3 4
3 3 4
1 2 7
3 4 5


5
6


cpp 代码如下：
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long lld;
const lld M = 100001;
lld arr1[M],arr2[M];
lld m,n,k;

//统计小于等于 mid 的个数
lld cntMin(lld mid){
lld cnt = 0;
lld j = n-1;
for(int i=0; i<m; i++){
//由于已排序，可直接利用上一次结果
while(j >= 0 && arr1[i] + arr2[j] > mid) j--;
cnt += j+1;
}
return cnt;
}

lld low,high,mid;
int main() {
while(scanf("%lld%lld%lld", &m,&n,&k) != EOF){
for(lld i=0; i<m; i++) scanf("%lld", &arr1[i]);
for(lld j=0; j<n; j++) scanf("%lld", &arr2[j]);
sort(arr1, arr1+m);
sort(arr2, arr2+n);
low  = arr1[0] + arr2[0];
high = arr1[m-1] + arr2[n-1];
lld ans;
//二分逼近
while(low <= high){
mid = (low+high)/2;
lld cnt = cntMin(mid);
if(cnt >= k){
ans = mid; //mid有可能是解
high = mid-1;
}else
low = mid+1;
}
printf("%lld\n",ans);

}
return 0;
}
/**************************************************************
Problem: 1534
User: coder
Language: C++
Result: Accepted
Time:830 ms
Memory:3080 kb
****************************************************************/