【題目描述】：有兩個正整數數列，元素個數分別為N和M。從兩個數列中分別任取一個數相乘，這樣一共可以得到N×M個數，詢問這N×M個數中第K小數是多少。 【輸入描述】：第一行為三個正整數N,M和K。第二行為N個正整數，表示第一個數列。第三行為M個正整數，表述第二個數列。 【輸出描述】：一個正整數表示第K小數。 【樣例輸入1】：2 3 4 1 2 2 1 3【樣例輸出1】：3【樣例輸入2】：5 5 18 7 2 3 5 8 3 1 3 2 5【樣例輸出2】：16【時間限制、數據范圍及描述】：時間：1s 空間：128M 編號__ N______ M_________ K______________ 元素大小(≤) 1 20 20 150 10^4 2 50 50 2000 10^4 3 100 80 5000 10^9 4 200 200 26000 10^9 5 10000 10000 50050000 10^4 6 1000 20000 9500000 10^4 7 1000 20000 10000500 10^9 8 2000 20000 190000 10^9 9 2000 20000 199000 10^9 10 20000 20000 210005000 10^4 11 20000 20000 210000 10^5 12 20000 20000 200000 10^9 13 20000 20000 220000500 10^5 14 20000 20000 199000500 10^9 15 200000 200000 180000 10^4 16 200000 200000 200000 10^9 17 2000 200000 100001500 10^9 18 200000 180000 19550000000 10^5 19 200000 200000 19900010000 10^9 20 200000 200000 20000010000 10^9本題直接二分一個數,然后在n*m個數中看比這個數小的數的個數是否小于等于k即可. 注意找比這個數小的數時,直接利用排序好的數列的階梯性質找即可,無需二次二分.Code: #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<ctime> using namespace std; const int N=200005; int n,m; long long k,a[N],b[N]; long long check(long long mid) {long long s=0,top=m;for(int i=1;i<=n;i++){long long now=mid/a[i];while(top>0&&b[top]>now){top--;}s+=top;}return s; } int main(){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+1+n);sort(b+1,b+1+m);long long l=a[1]*b[1],r=a[n]*b[m];while(l<r) {long long mid=(l+r)/2;if(check(mid)>=k){r=mid;}else{l=mid+1;}}printf("%lld\n",l);return 0; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11503969.html

總結

以上是生活随笔為你收集整理的UOJ #576. 积的第K小数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。