九度OJ 1534 數(shù)組中第K小的數(shù)字
來源：程序員人生 發(fā)布時間：2015-01-09 08:12:06 閱讀次數(shù)：2831次
題目1534：數(shù)組中第K小的數(shù)字
時間限制：2 秒
內(nèi)存限制：128 兆
特殊判題：否
提交：1524
解決：307
-
題目描寫：
-
給定兩個整型數(shù)組A和B。我們將A和B中的元素兩兩相加可以得到數(shù)組C。
比方A為[1,2]，B為[3,4].那末由A和B中的元素兩兩相加得到的數(shù)組C為[4,5,5,6]。
現(xiàn)在給你數(shù)組A和B，求由A和B兩兩相加得到的數(shù)組C中，第K小的數(shù)字。
-
輸入：
-
輸入可能包括多個測試案例。
對每一個測試案例，輸入的第1行動3個整數(shù)m，n， k(1<=m,n<=100000， 1<= k <= n *m)：n，m代表將要輸入數(shù)組A和B的長度。
緊接著兩行， 分別有m和n個數(shù)， 代表數(shù)組A和B中的元素。數(shù)組元素范圍為[0,1e9]。
-
輸出：
-
對應(yīng)每一個測試案例，
輸出由A和B中元素兩兩相加得到的數(shù)組c中第K小的數(shù)字。
-
樣例輸入：
-
2 2 3
1 2
3 4
3 3 4
1 2 7
3 4 5
-
樣例輸出：
-
5
6
-
來源：
- Google面試題
真心的，google面試題真難，(⊙o⊙)…
#include <stdio.h>
#include <stdlib.h>
long long m, n;
long long k;
long long A[100000], B[100000];
long long i;
int compare(const void * p, const void * q){
return *(long long *)p - *(long long *)q;
}
long long cal (long long mid){//這個雖然和cal2 有相同的輸出，可是做了很多的無用計算，會超時
long long i, j;
long long cnt = 0;
j=0;
for(i=0;i<m;++i)
{
j=0;//每次都要初始化為0，重新開始計數(shù)
while(j<n&&A[i]+B[j]<=mid)
++j;
cnt+=j;
}
return cnt;
}
long long cal2 (long long mid){
/*本函數(shù)能夠節(jié)省沒必要要的計算值，A從小到大遍歷，B從大到小遍歷便可，
假設(shè)A[i]+B[j]<=mid了，那末此時的j對i+1來說，范圍還是有些大了，繼續(xù)遞減j，便可，那末從始至終，j只需要從n⑴到0便可。
*/
long long i, j;
long long cnt = 0;
j = n - 1;
for (i=0; i<m; ++i){
while (j>=0 && A[i]+B[j]>mid)
--j;
cnt += (j + 1);
}
return cnt;
}
long long findKth (long long k){
long long min = A[0] + B[0];
long long max = A[m - 1] + B[n - 1];
long long mid;
long long ans;
while (min <= max){
mid = (max - min)/2 + min;
long long b=cal2(mid);
//long long b=cal(mid);//無用計算太多，會超時
if (k <= b){
max = mid - 1;
}
else
min = mid + 1;
}
return min;
}
int main(void){
while (scanf ("%lld%lld%lld", &m, &n, &k) != EOF){
for (i=0; i<m; ++i)
scanf ("%lld", &A[i]);
for (i=0; i<n; ++i)
scanf ("%lld", &B[i]);
qsort (A, m, sizeof(long long), compare);
qsort (B, n, sizeof(long long), compare);
printf ("%lld
", findKth(k));
}
return 0;
}
/**************************************************************
Problem: 1534
User: kirchhoff
Language: C
Result: Accepted
Time:960 ms
Memory:3256 kb
****************************************************************/
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
