POJ - 3685 Matrix-白红宇

POJ - 3685 Matrix

阅读量：5068 次

发布时间：2019-06-12

本文共 1606 字，大约阅读时间需要 5 分钟。

二分kth，答案满足的条件为：m ≤ 小于等于x的值数cnt_x。x和cntx单调不减，随着x增大，条件成立可表示为：0001111。

本地打一个小型的表可以发现列编号j固定时候，目标函数f(i,j)似乎具有单调性。

变形，f(i,j) = (i+100000+j)*i + j² - 100000，可以看出确实具有单调性。

于是得到如下算法：二分x，统计cnt时候，枚举j，再套一个二分。

/**********************************************************            ------------------                          **   author AbyssalFish                                   ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;ll n, m;const int d = 1e5;inline ll f(ll j,ll i){ return (i+d+j)*i + (j-d)*j; }int upp_b(ll j, ll x){ if(f(j,1) > x) return 0; int lb = 1, ub = n, md; while(lb < ub ){ md = (lb+ub+1)>>1; //f(j,md)>x? ub = md+1:lb = md+1; f(j,md)<=x? lb = md:ub = md-1; } return lb;}ll solve(){ if(m == 1) { ll ans = (3*n+d)*n; for(ll j = 1; j <= n; j++){ ans = min(ans, (1+d+j)+(j-d)*j); } return ans; } if(m == n*n){ ll ans = -(3*n+d)*n; for(ll j = 1; j <= n; j++){ ans = max(ans, (n+d+j)*n-d*j+j*j); } return ans; } ll lb = -(3*n+d)*n, ub = -lb, md; while(lb < ub){ md = (lb+ub)>>1; ll upb = 0; for(ll j = 1; j <= n; j++){ upb += upp_b(j,md); } upb >= m?ub = md:lb = md+1; } return lb;}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int T; scanf("%d",&T); while(T--){ scanf("%I64d%I64d",&n,&m); printf("%I64d\n", solve()); } return 0;}