Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


第K小数

题目描述

有两个正整数数列,元素个数分别为N和M。从两个数列中分别任取一个数相乘,这样一共可以得到NM个数,询问这NM个数中第K小数是多少。

输入格式

输入文件名为number.in。
输入文件包含三行。
第一行为三个正整数N,M和K。
第二行为N个正整数,表示第一个数列。
第三行为M个正整数,表述第二个数列。

输出格式

输出文件名为number.out。
输出文件包含一行,一个正整数表示第K小数。


解题思路

20%做法:直接相乘后排序
75%做法:对于第二个数组排序,先二分答案k然后枚举第一个数组的N个数,设为a[i],在第二个数组中再二分,计算有多少个数b与a[i]相乘小于等于k,最后统计并与k比较。时间复杂度O(NlogQlogM)
100%做法:对两个数组都排序,还是县二分答案k,显然当a[i]相乘小于等于k的b的个数在递减,弄一个下标指针,这样第二重二分就可以省去。时间复杂度(O(N+M)*logQ)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cmath>
#include<deque>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define range 200010
#define ll long long
using namespace std;
ll a[range],b[range],k;
int n,m;
ll read(ll x){
x=0;ll flag=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*flag;
}
bool check(ll mid){
ll p = n,sum = 0;
for(ll i = 1;i <= m;i++){
while(b[i]*a[p] > mid && p) p--;
sum+=p;
}
if(sum >= k)return true;
return false;
}
int main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%d%d%lld",&n,&m,&k);;
for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
for(int i = 1;i <= m;i++) scanf("%lld",&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+m+1);
ll l=0,r=a[n]*b[m]+5,ans;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%lld",ans);
return 0;
}
最近的文章

qbxt Day1 解题报告

上午==&gt;T1 立方数题目描述 LYK定义了一个数叫“立方数”,若一个数可以被写作是一个正整数的3次方,则这个数就是立方数,例如1,8,27就是最小的3个立方数。现在给定一个数P,LYK想要知道这个数是不是立方数。当然你有可能随机输出一些莫名其妙的东西来骗分,因此LYK有T次询问~ 输入格 …

于 继续阅读
更早的文章

【UER#2】手机的生产

传送门题目链接 由于电信技术的发展,人人都可以通过手机互相联系。 有一位电信大佬最近想生产一大批手机,然而从生产线上一台一台地生产实在太慢了,于是他想出了一个办法 —— 让手机自我复制。 于是他给手机加上了一个内置的函数 fork()。手机的程序如果调用这个函数,那么手机会生产出一台完全一模一样的手 …

于 继续阅读