Google 面试题 第K小的数字 二分逼近&二分查找
#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() {freopen("in.txt", "r", stdin);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;}elselow = mid+1;}printf("%lld\n",ans);}return 0;}
?
转自：http://www.acmerblog.com/offer-google-2-1173/
