POJ3685 Matrix —— 二分

时间：2023-03-09 16:45:38
POJ3685 Matrix —— 二分

题目链接：http://poj.org/problem?id=3685

Matrix
Time Limit: 6000MS   Memory Limit: 65536K
Total Submissions: 7378   Accepted: 2187

Description

Given a N × N matrix A, whose element in the i-th row and j-th column Aij is an number that equals i2 + 100000 × i + j2 - 100000 × j + i × j, you are to find the M-th smallest element in the matrix.

Input

The first line of input is the number of test case.
For each test case there is only one line contains two integers, N(1 ≤ N ≤ 50,000) and M(1 ≤ M ≤ N × N). There is a blank line before each test case.

Output

For each test case output the answer on a single line.

Sample Input

12

1 1

2 1

2 2

2 3

2 4

3 1

3 2

3 8

3 9

5 1

5 25

5 10

Sample Output

3

-99993

3

12

100007

-199987

-99993

100019

200013

-399969

400031

-99939

Source

题解：
1.二分这个数mid，然后计算有多少对（i，j），使得F= i^2 + 100000 × i + j^2 - 100000 × j + i × j <= mid。如果符合，则缩小mid，否则增大mid。
2.问：怎么计算有多少对（i，j）使得 F <= mid 呢？
答：根据观察，式子“F =  i^2 + 100000 × i + j^2 - 100000 × j + i × j”为二元二次方程，当i确定时，F就成了关于j的一元二次方程。所以枚举i，然后计算 有多少个整数j，使得 F = j^2 + (i-1e5)*j + i^2 + i*1e5 - mid <= 0。根据高中的知识，我们需要求解出函数F的两个零点x1和x2（1<=x1<=x2<=n），然后再从区间[x1,x2]取出整数，即得到了满足约束的多对（i，j）。
正确代码：（求最小的数，使得小于等于它的数的个数>=m。即为题目所求）
 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 #define ms(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const LL LNF = 2e18;

 const int MAXN = 1e3+;

 LL n, m;

 bool test(LL tmp)

 {

     LL sum = ;

     for(LL i = ; i<=n; i++)    //枚举i。当i已确定时， 剩下的式子就是关于j的一元二次方程。求解两个根。

     {

         LL a = , b = i-, c = 1LL*i*i+1LL*i*-tmp;

         if(1LL*b*b-4LL*a*c<) continue; //无实数根时， 下一个i

         LL x1 = max( 1LL, (LL)ceil((-b-sqrt(1LL*b*b-4LL*a*c))/(*a)) ); //左根向上取整，最小只能为1。

         LL x2 = min( 1LL*n, (LL)floor((-b+sqrt(1LL*b*b-4LL*a*c))/(*a)) );  //右根向下取整，最大只能为n

         sum += max( 0LL, x2-x1+ ); //区间内有多少个整数

     }

     return sum>=m;

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%lld%lld", &n, &m);

         LL l = -2e10, r = 2e10;

         while(l<=r)     //二分答案

         {

             LL mid = (l+r)>>;

             if(test(mid))

                 r = mid - ;

             else

                 l = mid + ;

         }

         printf("%lld\n", l);

     }

 }

错误代码：（求最大的数，使得小于它的数的个数<m。为题目所求的上一个数）

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 #define ms(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const LL LNF = 2e18;

 const int MAXN = 1e3+;

 LL n, m;

 bool test(LL tmp)

 {

     LL sum = ;

     for(LL i = ; i<=n; i++)    //枚举i。当i已确定时， 剩下的式子就是关于j的一元二次方程。求解两个根。

     {

         LL a = , b = i-, c = 1LL*i*i+1LL*i*-tmp;

         if(1LL*b*b-4LL*a*c<=) continue;

         LL x1 = max( 1LL, (LL)ceil((-b-sqrt(1LL*b*b-4LL*a*c))/(*a)) ); //左根向上取整，最小只能为1。

         LL x2 = min( 1LL*n, (LL)floor((-b+sqrt(1LL*b*b-4LL*a*c))/(*a)) );  //右根向下取整，最大只能为n

         sum += max( 0LL, x2-x1+ ); //区间内有多少个整数

     }

     return sum<m;

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%lld%lld", &n, &m);

         LL l = -2e10, r = 2e10;

         while(l<=r)     //二分答案

         {

             LL mid = (l+r)>>;

             if(test(mid))

                 l = mid + ;

             else

                 r = mid - ;

         }

         printf("%lld\n", r);

     }

 }

相关文章