怎么把網(wǎng)站提交,鄭州市城鄉(xiāng)建設(shè)規(guī)劃網(wǎng)站,企業(yè)seo外包,網(wǎng)站域名必須備案嗎小紅的矩陣 時間限制#xff1a;1秒 空間限制#xff1a;256M 網(wǎng)頁鏈接 牛客tracker ?？蛅racker 每日一題#xff0c;完成每日打卡#xff0c;即可獲得牛幣。獲得相應(yīng)數(shù)量的牛幣#xff0c;能在【牛幣兌換中心】#xff0c;換取相應(yīng)獎品#xff01;助力每日有…小紅的矩陣時間限制1秒 空間限制256M網(wǎng)頁鏈接?？蛅racker?？蛅racker 每日一題完成每日打卡即可獲得牛幣。獲得相應(yīng)數(shù)量的牛幣能在【牛幣兌換中心】換取相應(yīng)獎品助力每日有題做豐盈牛幣日益多!題目描述小紅有一個n × m n×mn×m大小的矩陣矩陣第i ii行第j jj列的元素為i × j i×ji×j小紅想知道矩陣中第k kk小的元素是多少。輸入描述第一行三個整數(shù)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。輸出描述輸出一個整數(shù)表示答案。示例1輸入3 3 4輸出3說明矩陣為1 2 32 4 63 6 9解題思路采用二分查找法確定矩陣中第k kk小的元素初始設(shè)置左邊界l 0 l0l0、右邊界r k rkrk因矩陣第k kk小元素必然不超過k kk每次取中間值m i d midmid統(tǒng)計矩陣中小于等于m i d midmid的元素數(shù)量遍歷每行i ii該行符合條件的列數(shù)為m i n ( m , m i d / i ) min(m, mid/i)min(m,mid/i)累加所有行的數(shù)量得到s u m sumsum若s u m ≥ k sum≥ksum≥k說明m i d midmid可能是目標(biāo)值或偏大調(diào)整右邊界r m i d ? 1 rmid-1rmid?1并將m i d midmid記為候選結(jié)果否則調(diào)整左邊界l m i d 1 lmid1lmid1該方法通過二分將問題轉(zhuǎn)化為多次統(tǒng)計每次統(tǒng)計時間復(fù)雜度O ( n ) O(n)O(n)二分次數(shù)約30 3030次總復(fù)雜度為O ( n l o g k ) O(nlogk)O(nlogk)適配n nn、m mm達1 e 5 1e51e5的規(guī)模最終候選結(jié)果即為矩陣中第k kk小的元素。代碼內(nèi)容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefpairll,llpii;constll p1e97;constll N1e510;intmain(){ll n,m,k;cinnmk;ll l0,rk;ll res0;while(lr){ll mid(lr)1;ll sum0;for(ll i1;in;i)summin(m,mid/i);if(sumk){rmid-1;resmid;}elselmid1;}coutresendl;return0;}