[编程题]小红的矩阵
题解：n×m 矩阵第 k 小元素题目分析问题描述给定 n×m 大小的矩阵，其中第 i 行第 j 列的元素为 i×j（1≤i≤n，1≤j≤m），要求找出矩阵中第 k 小的元素。分析题干矩阵规模极大（n,m≤1e5），直接生成矩阵会占用 O (nm) 空间，完全超出内存限制；暴力排序所有元素更是不可能（
展开全文
观察到数据范围很大，不能暴力找既然说了找到第k小，我们就想到一个高效率的查找：二分查找如何计算每一行中小于k的个数呢首先一行至多m个，根据题目公式i*j,我们假定找到的数为mid，有i*j<=mid也就是j<=mid/i；对每一行统计，得到最终结果并且更新答案就好了
int main()
展开全文
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int k, l, r, mid, sum;
inline int min(int a, int b)
{
return a
展开全文
二分遍历(O(nlog(n*m)) 思路可以参考其他题解, 此题解思路在此基础上进行了一点升级, 使用了数论分块加速
我们观察二分的 check 函数, 其返回值为:
注意到计算 是数论分块的经典问题
因此我们 check 函数的遍历可以使用数论分块思路加速
数论分块思路简单来说, 就是根据
展开全文
#include <iostream>
#include <vector>
using namespace std;
//注意精度
int main() {
long long n, m, k;
cin >> n >> m >>
展开全文
核心思想：二分答案
确定数值范围：矩阵中最小的元素是 ，最大的元素是 。我们要找的第 小的数一定在这个区间 内。
单调性分析：如果我们选定一个数值 ，我们可以很容易地计算出矩阵中有多少个元素是小于等于 的。
如果小于等于 的元素个数 ，说明第 小的数一定在 范围内（即 可能是答案，
展开全文
题目链接
小红的矩阵
题目描述
给定一个 大小的矩阵，矩阵第 行第 列的元素为 。小红想知道矩阵中第 小的元素是多少。
解题思路
这是一个在概念矩阵（Conceptual Matrix）中寻找第 小元素的问题。
1. 暴力解法的局限性
由于 和 的范围可达 ，矩阵的大小可能达到 。直接
展开全文
n, m, k = map(int, input().split())
def count(x):
s = 0
for i in range(1, n + 1):
s += min(m, x // i)
return s
l, r = 1, n * m
w
展开全文
def foll(n,m,k):
if n<m :
n,m=m,n
left=1
right = n * m
while left<right:
mid = (left+right)//2
count=0
展开全文
问题信息
难度：
4条回答
22收藏
25浏览
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
