欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分套二分---poj 3685 Matrix(注意观察式子);

程序员文章站 2024-03-17 15:22:04
...

二分套二分—poj 3685 Matrix

题目链接:http://poj.org/problem?id=3685
二分套二分---poj 3685 Matrix(注意观察式子);

二分套二分---poj 3685 Matrix(注意观察式子);

二分套二分---poj 3685 Matrix(注意观察式子);

题意:

​ 一个正方形矩阵,每次询问先给出边长n,然后在矩阵里面的数每一个都满足上面的那个式子,之后会给出一个k,代表要求这个矩阵里的第k小数。

解题思路:
仔细观察这个式子发现,当i固定的时候,函数是随着j递减的,当j是固定的时候,函数是随着i递增的;

所以我们可以遍历整个矩阵,找出那个只有(k-1)个数比那个数小的数就行;

不过仔细一想,这样遍历绝对超时,后来看到博客才知道还有二分套二分的思想;

具体就是我们先假设一个数是第k小数,然后把他带到矩阵里面去找比他小的个数,然后和k进行比较;

上面的是第一重二分,第二重二分的方法如下:

​ 我先遍历每一行,然后因为上面说过的在同行递减,同列递增,所以我们可以找出在某一行的第一个比这个数大的数的第一个位置,同时我们也计算出在这一行或者这一列里面比它小的数有多少个,这样遍历全部列||全部行就可以得出结果。

具体代码如下:


#include<stdio.h>
const int inf=1e9;
#define ll long long
const int c=100000;
ll f(ll x,ll y)
{
   return (x*x+c*x+y*y-c*y+x*y);
}
ll n,m;

ll check(ll  num)//该函数的功能就是找出矩阵里面有多少个数比num小 
{
   ll cnt=0;
   for(int i=1;i<=n;i++)//枚举列
   {
      ll s1=1,s2=n;
      int ant=0;
      while(s1<=s2)//二分找出比num小的个数
      {
         ll smid=(s1+s2)/2;
         if(f(smid,i)<=num)
         {
            ant=smid;
            s1=smid+1;
         }
         else s2=smid-1;
      }
      cnt+=ant;
   }
   return cnt;
}

int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%lld%lld",&n,&m);
      ll l=-100000*n,r=n*n+100000*n+n*n+n*n;//将左右变量尽量设大
      ll ans;
      while(l<=r)
      {
         ll mid=(l+r)/2;
         if(check(mid)>=m)
         {
            ans=mid;
            r=mid-1;
         }
         else l=mid+1;
      }
      printf("%lld\n",ans);
   }
   return 0;
}

总结:
当时看着这个式子的时候感觉无从下手,后来用把数据小的矩阵打了出来

发现它是从对角线那里有整体递增的规律,但是后来发现这样写好像很难处理。emmm总的来说,还是见的太少了,对二分的认识也只停留在那个有序数列的查找中,还有对式子的观察不够仔细。希望通过训练来提高自己。