POJ_3685_Matrix_(二分,查找第k大的值)

描述

一个n*n的矩阵,(i,j)的值为i*i+100000*i+j*j-100000*j+i*j,求第m小的值.

Matrix

Time Limit: 6000MS		Memory Limit: 65536K
Total Submissions: 5980		Accepted: 1700

Description

Given a N × N matrix A, whose element in the i-th row and j-th column A_ij is an number that equals i² + 100000 × i + j² - 100000 × j + i × j, you are to find the M-th smallest element in the matrix.

Input

The first line of input is the number of test case.
For each test case there is only one line contains two integers, N(1 ≤ N ≤ 50,000) and M(1 ≤ M ≤ N × N). There is a blank line before each test case.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

Source

POJ Founder Monthly Contest – 2008.08.31, windy7926778

分析

与POJ_3579很像.假定一个第m小的值x,如果<=x的值<m,那么x偏小.在统计<=x的值的时候还要用到二分,对于一个确定的j,值是关于i单增的,枚举j,二分查找使得值<=x的最大的i.

注意:

1.第一层二分的边界:最大值是i,j取n,去掉负值;最小值是i,j取n,去掉正值.

2.第二层二分统计个数时,i在(1,n)内不一定存在使得值<=x的,所以二分范围不能是(1.n).如x=-1,n=1,如果在(1,n)内,值只有3,这样最后l=r=1,表示有一个<=x的值,其实一个都没有,所以应该在(0,n)内二分,而这里因为写成了m=l+(r-l+1)/2,有一个"+1",所以(r-l+1)/2>=1,m>=1,所以不必担心会去到0,如果不是这样,在val函数中应加一条:if(i==0) return -100000*n;也就是给0的情况一个最小值,如果有n+1,应赋最大值.也就是假设了左右两个端点,最后如果落在这两个实际不存在的点上,那么就是没有答案.

3.数据范围.整型上限大概2*10^9,这道题极限情况1.75*10^10,必须用long long.检查的时候还是要耐心.

 1 #include<cstdio>
 2 #define ll long long
 3 
 4 ll q,n,m;
 5 
 6 ll val(ll i,ll j){ return i*i+100000*i+j*j-100000*j+i*j; }
 7 
 8 ll bsearch(ll j,ll x)
 9 {
10     ll l=0,r=n;
11     while(l<r)
12     {
13         ll m=l+(r-l+1)/2;
14         if(val(m,j)<=x) l=m;
15         else r=m-1;
16     }
17     return l;
18 }
19 
20 bool C(ll x)
21 {
22     ll cnt=0;
23     for(ll j=1;j<=n;j++) cnt+=bsearch(j,x);
24     return cnt<m;
25 }
26 
27 void solve()
28 {
29     ll l=-100000*n,r=3*n*n+100000*n;
30     while(l<r)
31     {
32         ll mid=l+(r-l)/2;
33         if(C(mid)) l=mid+1;
34         else r=mid;
35     }
36     printf("%lld
",l);
37 }
38 
39 void init()
40 {
41     scanf("%lld",&q);
42     while(q--)
43     {
44         scanf("%lld%lld",&n,&m);
45         solve();
46     }
47 }
48 
49 int main()
50 {
51     freopen("matrix.in","r",stdin);
52     freopen("matrix.out","w",stdout);
53     init();
54     fclose(stdin);
55     fclose(stdout);
56     return 0;
57 }

View Code