POJ3685 為啥二分答案的時候，L用-INF,R用INF WA了 然后看別人代碼 發現別人的代碼和思路和我的完全完全一樣！！就是L變成了-1e12,R變成了1e12，就AC了，這是為什么啊？？？？具體的看下面代碼里唯一的一處標記
最近在做二分的題目，我已經不是一次因為這個錯了，但是L和R的范圍咱也不可能一個一個地試，一般也就算個大概范圍就完了，畢竟有while回圈在呢，可是這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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/140704.html
標籤：C++ 語言
上一篇：求助，C語言素數