Leetcode378原题，所以一样没有数据范围…(

  • log(max-min)二分答案，然后NlogN二分每一行求出小于答案的元素个数，为了保证二分的答案在矩阵中，二分写的要和平常不太一样，最后输出的是l。
  • 感觉这是个经典题应该有更好的方法，但是搜了一圈好像没有…

code

#include <bits/stdc++.h>
using  namespace std;
const int N=1e4+50;
int a[N][N];
int k,n;
int count(int x){
    int ans=0;
    for(int i=1;i<=n;i++){
        int l=1,r=n;
        int cnt=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(a[i][mid]<=x){
                cnt=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        ans+=cnt;
    }
    return ans;
}
int main(){
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int l=a[1][1],r=a[n][n];
    while(l<r){
        int mid=(l+r)/2;
        int cnt=count(mid);
        if(cnt<k){
            l=mid+1;
        }else{
            r=mid;
        }
    }
    printf("%d\n",l);
    return 0;
}

版权声明：本文为zxcoder原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/zxcoder/p/12261679.html