POJ3685 为啥二分答案的时候,L用-INF,R用INF WA了 然后看别人代码 发现别人的代码和思路和我的完全完全一样!!就是L变成了-1e12,R变成了1e12,就AC了,这是为什么啊????具体的看下面代码里唯一的一处标记
最近在做二分的题目,我已经不是一次因为这个错了,但是L和R的范围咱也不可能一个一个地试,一般也就算个大概就完了,可是这POJ上许多题你不按博客题解上的范围搞就是会WA,就拿这道题来看看吧,实在忍受不了了,求大神们指点一下,小弟感激不尽啊!!!
看问题:
Descriptions
有一个N阶方阵 第i行,j列的值Aij =i2 + 100000 × i + j2 - 100000 × j + i × j,需要找出这个方阵的第M小值.
Input
第一行输入T代表测试组数.
每个测试用例包含2个数字N,M表示在N阶方阵找出第M大值, N(1 ≤ N ≤ 50,000) and M(1 ≤ M≤ N × N). 每两个测试用例之间可能有空行
Output
输出方阵的第M小值
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
题目链接
https://vjudge.net/problem/POJ-3685
代码:
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
using namespace std;
int dt[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};
//typedef pair<int, int> P;
//priority_queue<int, vector<int>, greater<int> > q;
ll T, n, m;
ll f(ll i, ll j);
ll judge(ll x);
int main()
{
cin >> T;
while (T--)
{
cin >> n >> m;
ll l = -1e12, r = 1e12, mid;//这里l用-INF,r用INF WA了 不知道为什么???
while (r - l > 1)
{
mid = (l + r) >> 1;
if (judge(mid) < m)
{
l = mid;
}
else
{
r = mid;
}
}
cout << l << endl;
}
}
ll f(ll i, ll j)
{
return i * i + 100000 * i + j * j - 100000 * j + i * j;
}
ll judge(ll x)
{
ll l, r, mid, sum = 0;
for (ll j = 1; j <= n; j++)
{
l = 0, r = n + 1;
while (r - l > 1)
{
mid = (l + r) >> 1;
if (f(mid, j) < x)
{
l = mid;
}
else
{
r = mid;
}
}
sum += l;
}
return sum;
}