题目链接:https://vjudge.net/problem/POJ-3685
题意:N阶方阵第i行,j列的值Aij =i2+100000×i+j2-100000×j+i×j,求这个方阵的第M小值
二分答案mid,如果直接O(n^2)暴力check会tle。观察到Aij对于i是递增的,对于j则没有单调性。那么判断有多少个数<=mid的过程中,可以枚举列数j。对于每个j,利用单调性二分求出有多少个i满足Aij<=mid,这样check的复杂度就降为O(nlogn)
#include<iostream> #define ll long long using namespace std; ll n,m,t,mid,lo,hi; ll calc(ll p,ll q){return p*p+1e5*p+q*q-1e5*q+p*q;} bool check(ll mid){ ll tot=0; ll l,r; for (ll j=1;j<=n;j++){ if (calc(n,j)<=mid) tot+=n; else { if (calc(1,j)>mid) continue; l=1;r=n; while (r-l>1){ ll mid2=(l+r)/2; if (calc(mid2,j)>mid) r=mid2;else l=mid2; } tot+=l; } } return tot>=m; } int main(){ cin>>t; while (t--){ cin>>n>>m; lo=-1e10; hi=1e11; while (hi-lo>1){ mid=(lo+hi)/2; if (check(mid)) hi=mid;else lo=mid; } cout<<hi<<endl; } }