小红的矩阵【牛客tracker 每日一题】

小红的矩阵

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多!

题目描述

小红有一个n × m n×mn×m大小的矩阵，矩阵第i ii行第j jj列的元素为i × j i×ji×j，小红想知道矩阵中第k kk小的元素是多少。

输入描述：

第一行三个整数n , m , k n,m,kn,m,k。
1 ≤ n , m ≤ 1 0 5 , 1 ≤ k ≤ n × m 1≤n,m≤10^5,1≤k≤n×m1≤n,m≤105,1≤k≤n×m。

输出描述：

输出一个整数表示答案。

示例1

输入：

3 3 4

输出：

3

说明：

矩阵为
1 2 3
2 4 6
3 6 9

解题思路

采用二分查找法确定矩阵中第k kk小的元素，初始设置左边界l = 0 l=0l=0、右边界r = k r=kr=k（因矩阵第k kk小元素必然不超过k kk），每次取中间值m i d midmid，统计矩阵中小于等于m i d midmid的元素数量（遍历每行i ii，该行符合条件的列数为m i n ( m , m i d / i ) min(m, mid/i)min(m,mid/i)，累加所有行的数量得到s u m sumsum）；若s u m ≥ k sum≥ksum≥k，说明m i d midmid可能是目标值或偏大，调整右边界r = m i d − 1 r=mid-1r=mid−1并将m i d midmid记为候选结果，否则调整左边界l = m i d + 1 l=mid+1l=mid+1；该方法通过二分将问题转化为多次统计，每次统计时间复杂度O ( n ) O(n)O(n)，二分次数约30 3030次，总复杂度为O ( n l o g k ) O(nlogk)O(nlogk)，适配n nn、m mm达1 e 5 1e51e5的规模，最终候选结果即为矩阵中第k kk小的元素。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;intmain(){ll n,m,k;cin>>n>>m>>k;ll l=0,r=k;ll res=0;while(l<=r){ll mid=(l+r)>>1;ll sum=0;for(ll i=1;i<=n;i++)sum+=min(m,mid/i);if(sum>=k){r=mid-1;res=mid;}elsel=mid+1;}cout<<res<<endl;return0;}