Bizon the Champion isn't just charming, he also is very smart.
While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann × m multiplication table, where the element on the intersection of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?
Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.
The single line contains integers n, m and k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m).
Print the k-th largest number in a n × m multiplication table.
2 2 2
2
2 3 4
3
1 10 5
5
A 2 × 3 multiplication table looks like this:
1 2 3 2 4 6
题意:
给出 n,m(1 ~ 5 * 10 ^ 5 ),k (1 ~ n * m ),代表有 n 行 m 列的数据,矩阵中的值为 i * j。求出矩阵中第 k 个大的数。
思路:
二分搜索。取区间为左开右闭区间,扫描每一行 num / i 的值有几个,算出的这个总数如果大于 k,不能说明这个数不是第 k 个大的数,因为可能会有重复的,但是如果这个总数小于 k,一定能说明这个数并非第 K 个大的数,所以这时候应该往右边搜,最后搜出来右区间的值即为答案。还有细节地方要处理就是 扫描每一行的时候要进行 min(num / i , m)操作,因为有可能除出来的数大于列数,那么加上的应该是这一行的列数个,而不是除数个。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; ll n, m, k, l, r; ll C (ll num) { ll ans = 0; for (ll i = 1; i <= n; ++i) ans += min((num / i), m); return ans; } void bit_search () { while (r - l > 1) { ll mid = l + (r - l) / 2; if (C(mid) < k) l = mid; else r = mid; } printf("%I64d\n", r); } int main() { scanf("%I64d%I64d%I64d", &n, &m, &k); l = 0; r = n * m; bit_search(); return 0; }
相关推荐
Multiplication_table.c
Java Program To Print Multiplication Table, Java Programming Tutorial Book
MultiplicationTable
乘法表最多可乘12的程序
the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n2:38) algebraic operations. The new algorithm is obtained using a surprisingly ...
Efficient matrix multiplication
语言:English (United States)下拉乘法表。下拉1至12的乘法表。在此更新中,我创建了一个更加“丰富多彩”的表。
// Included Java code snippets for sorting,swapping,Threading,multiplication Table and Pattern printing
下拉乘法表。 简单的下拉乘法表就地乘法。 版本日志: V 1.0 12/07/2013最初发布到Chrome网上商店 版权和许可 版权所有2013 Peckitt Software 根据Apache许可证2.0版(“许可证”)获得许可;除遵守许可证外,不得...
■Topics covered last time: —int eger addition —carr y lookah ead addition —stan dar d int eger mu ltiplicat ion —carr y-save addition of thr ee vectors: sum s ar e saved in one vector, carr ies ...
Modular Multiplication Without Trial Division。By Peter L. Montgomery。蒙哥马利模乘的论文。
multiplication-table:使用HTML,CSS和JavaScript进行的10 x 10倍表的审阅和测验
乘法表-通过LexusCreations 学习无限乘法表-简单JavaScript应用访问-https:
Source Code for 2009 Supercomputing Paper Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors
打印九九乘法表java 8Multiplication table.rar 打印九九乘法表java 8Multiplication table.rar
booth在1950年发表的关于booth算法的论文。感兴趣可参考。
Batched Sparse Matrix Multiplication for Accelerating Graph Convolutional Networks 对图卷积网络进行加速的批量稀疏矩阵乘法 作者的ppt的pdf版本
Matrix_multiplication.c
1.自动随机生成5000*5000的2个矩阵 2.使用MPI对矩阵相乘进行并行处理 3.加速比接近10倍