九度OJ 1534 数组中第K小的数字
发布时间：2020-12-13 20:11:32 所属栏目：PHP教程 来源：网络整理
导读：题目1534：数组中第K小的数字 时间限制： 2 秒 内存限制： 128 兆 特殊判题： 否 提交： 1524 解决： 307 题目描写： 给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。 比方A为[1,2]，B为[3,4].那末由A和B中的元素两两相加得到的数组C为[4,
|
#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，重新开始计数
while(j<n&&A[i]+B[j]<=mid)
++j;
cnt+=j;
}
return cnt;
}
long long cal2 (long long mid){
/*本函数能够节省没必要要的计算值，A从小到大遍历，B从大到小遍历便可，
假设A[i]+B[j]<=mid了，那末此时的j对i+1来说，范围还是有些大了，继续递减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,compare);
printf ("%lld
",findKth(k));
}
return 0;
}
/**************************************************************
Problem: 1534
User: kirchhoff
Language: C
Result: Accepted
Time:960 ms
Memory:3256 kb
****************************************************************/
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |