- Matrix
- 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
在 main 函数中
设 mid 为 N 阶方阵中第 sum 小的数, 若 sum<M, 则 mid 小了
若 sum>M, 则 mid 大了
在 judge 函数中
(mid,j) 即为 (i,j), 一列一列的找有 mid 个数比 value 小, 再把每一列的 mid 加一起, 即可得出在 N 阶方阵中比 value 小的数的个数 sum
AC 代码
- #include <iostream>
- #include <cstdio>
- #include <fstream>
- #include <algorithm>
- #include <cmath>
- #include <deque>
- #include <vector>
- #include <queue>
- #include <string>
- #include <cstring>
- #include <map>
- #include <stack>
- #include <set>
- #include <sstream>
- #define iOS ios_base::sync_with_stdio(0); cin.tie(0);
- #define Mod 1000000007
- #define eps 1e-6
- #define ll long long
- #define INF 0x3f3f3f3f
- #define MEM(x,y) memset(x,y,sizeof(x))
- #define Maxn 100000+5
- using namespace std;
- ll T,n,m;
- ll fun(ll i,ll j)// 求值
- {
- return i*i+100000*i+j*j-j*100000+i*j;
- }
- ll judge(ll value)
- {
- ll l,r,mid,sum;
- sum=0;
- for(ll j=1;j<=n;j++)
- {
- l=0,r=n+1;
- while(r-l>1)
- {
- mid=(l+r)/2;
- if(fun(mid,j)<value)
- l=mid;
- else
- r=mid;
- }
- sum+=l;
- }
- return sum;
- }
- int main()
- {
- scanf("%lld",&T);
- while(T--)
- {
- scanf("%lld",&n);
- scanf("%lld",&m);
- ll l,r,mid;
- l=-1e12,r=1e12;// 设置上下界
- while(r-l>1)
- {
- mid=(l+r)/2;
- if(judge(mid)<m)
- l=mid;
- else
- r=mid;
- }
- printf("%lld\n",l);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3147474.html