ANTFANAAA 2020-02-21 01:53 采纳率: 0%
浏览 408

POJ3685 为啥二分答案的时候,L用-INF,R用INF WA了 然后看别人代码 发现别人的代码和思路和我的完全完全一样!!就是L变成了-1e12,R变成了1e12,就AC了,这是为什么啊????

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;
}

  • 写回答

1条回答 默认 最新

  • 一生只爱利物浦� 2021-03-15 23:43
    关注

    你这个inf是对于int的inf,答案早就爆int了

    评论

报告相同问题?

悬赏问题

  • ¥15 kafka 分区副本增加会导致消息丢失或者不可用吗?
  • ¥15 微信公众号自制会员卡没有收款渠道啊
  • ¥15 stable diffusion
  • ¥100 Jenkins自动化部署—悬赏100元
  • ¥15 关于#python#的问题:求帮写python代码
  • ¥20 MATLAB画图图形出现上下震荡的线条
  • ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
  • ¥15 perl MISA分析p3_in脚本出错
  • ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
  • ¥15 ubuntu虚拟机打包apk错误