POJ-3685 Matrix---二分套二分

题目链接：

https://cn.vjudge.net/problem/POJ-3685

题目大意：

给出一个N*N的矩阵A，A[i][j]的值等于i² + 100000 ×i + j² - 100000 × j + i × j，求这个矩阵中第M小的数

解题思路：

此处需要二分第M值，设为x，然后再判断x是不是至少有M个比它小的元素。这样就可以进行二分

求出比x小的元素的个数时，可以枚举j，二分有多少个i满足，因为当j为定值的时候，函数就变成：

i² + (100000 + j) * ×i + j² - 100000 × j

i在1-50000是递增的，所以可以枚举j，求出有多少个i满足条件

然而i为定值时：

j² + (i- 100000) × j + i² + 100000 ×i

这里j在1-50000中有部分不是递增的，所以只能枚举j，二分i

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 typedef long long ll;
 8 const ll INF = 1e12;
 9 const int maxn = 1e5 + 10;
10 ll a[maxn], n, m;
11 ll f(ll x, ll y)
12 {
13     return x * x + 100000 * x + y * y - 100000 * y + x * y;
14 }
15 ll ok(ll mid)
16 {
17     ll ans = 0;
18     for(int j = 1; j <= n; j++)//枚举j，这样函数值和i单调递增
19     {
20         ll l = 1, r = n, idx = 0;
21         while(l <= r)
22         {
23             ll m = (l + r) / 2;
24             if(f(m, j) <= mid)
25             {
26                 idx = m;
27                 l = m + 1;
28             }
29             else r = m - 1;
30         }
31         ans += idx;
32     }
33     return ans;
34 }
35 int main()
36 {
37     int T;
38     cin >> T;
39     while(T--)
40     {
41         scanf("%lld%lld", &n, &m);
42         ll l = -INF, r = INF, ans;
43         while(l <= r)
44         {
45             ll mid = (l + r) / 2;
46             if(ok(mid) >= m)//小于等于mid的数字个数 >= m 说明mid>=最优解
47             {
48                 ans = mid;
49                 r = mid - 1;
50             }
51             else l = mid + 1;
52         }
53         printf("%lld
", ans);
54     }
55     return 0;
56 }