poj 3685 Matrix(二分搜索之查找第k大的值)

Description

Given a N × N matrix A, whose element in the i-th row and j-th column Aij is an number that equals i2 + 100000 × i + j2 - 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

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

Source

POJ Founder Monthly Contest – 2008.08.31, windy7926778 

 题目大意:题目意思很简单。这个题目乍一看,先打n为比较小例如8的表,会觉得很有规律,大小规律是从右上往左下依次增大,但是这个规律到n为5*10^4就不一定保持了。

           解题思路:有一个规律是看得见的,j不变i增大函数值也在增大。根据这个可以对这n列二分得到<x的值,同样所求的x也是可以二分慢慢靠近最后的结果,我处理得到最后的结果是个数为m+1的最小值,所以最后mid-1即为答案。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<math.h>
 6 #include<stdlib.h>
 7 using namespace std;
 8 #define inf 1<<30
 9 #define ll long long
10 #define N 50006
11 ll n,m;
12 ll cal(ll i,ll j){
13     return i*i+100000*i+j*j-100000*j+i*j;
14 }
15 bool solve(ll mid){
16     ll cnt=0;
17     for(ll j=1;j<=n;j++){
18         ll low=1;
19         ll high=n+1;
20         while(low<high){
21             ll tmp=(low+high)>>1;//另外的写法
22             ll ans=cal(tmp,j);
23             if(ans>=mid){
24                 high=tmp;
25             }
26             else{
27                 low=tmp+1;
28             }
29         }
30         cnt+=low-1;//另外的写法
31     }
32     if(cnt>=m) return true;
33     return false;
34 }
35 int main()
36 {
37     int t;
38     scanf("%d",&t);
39     while(t--){
40
41         scanf("%I64d%I64d",&n,&m);
42         ll low=-1e12;
43         ll high=1e12;
44
45         while(low<high){
46             ll mid=(low+high)>>1;//另外的写法
47             if(solve(mid)){
48                 high=mid;
49             }
50             else{
51                 low=mid+1;
52             }
53         }
54         printf("%I64d\n",low-1);//另外的写法
55
56     }
57     return 0;
58 }

另外的写法,试比较

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<math.h>
 6 #include<stdlib.h>
 7 using namespace std;
 8 #define inf 1<<30
 9 #define ll long long
10 #define N 50006
11 ll n,m;
12 ll cal(ll i,ll j){
13     return i*i+100000*i+j*j-100000*j+i*j;
14 }
15 bool solve(ll mid){
16     ll cnt=0;
17     for(ll j=1;j<=n;j++){
18         ll low=1;
19         ll high=n+1;
20         ll tmp=(low+high)>>1;
21         while(low<high){
22             ll ans=cal(tmp,j);
23             if(ans>=mid){
24                 high=tmp;
25             }
26             else{
27                 low=tmp+1;
28             }
29             tmp=(low+high)>>1;
30         }
31         cnt+=tmp-1;
32     }
33     if(cnt>=m) return true;
34     return false;
35 }
36 int main()
37 {
38     int t;
39     scanf("%d",&t);
40     while(t--){
41
42         scanf("%I64d%I64d",&n,&m);
43         ll low=-1e12;
44         ll high=1e12;
45         ll mid=(low+high)>>1;
46         while(low<high){
47             if(solve(mid)){
48                 high=mid;
49             }
50             else{
51                 low=mid+1;
52             }
53             mid=(low+high)>>1;
54         }
55         printf("%I64d\n",mid-1);
56
57     }
58     return 0;
59 }

时间: 09-02

poj 3685 Matrix(二分搜索之查找第k大的值)的相关文章

poj 3579 Median (二分搜索之查找第k大的值)

Description Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i < j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly

查找第K大的值

这种题一般是给定N个数,然后N个数之间通过某种计算得到了新的数列,求这新的数列的第K大的值 POJ3579 题意: 用$N$个数的序列$x[i]$,生成一个新序列$b$. 新的序列定义为:对于任意的$ i$,$j$且 $i != j $有$b[] = abs(x[i] - x[j])$ 问新序列的中位数是什么,如果新序列的长度为偶数那么我们定义中位数为排序后第len/2位置的那个数 解法: 相当于问新序列中的第K大的数多少. 注意新数列不可能全都算出来. 二分答案,二分那个第K大的数的值. $x

POJ 3579 3685(二分-查找第k大的值)

POJ 3579 题意 双重二分搜索:对列数X计算∣Xi – Xj∣组成新数列的中位数 思路 对X排序后,与X_i的差大于mid(也就是某个数大于X_i + mid)的那些数的个数如果小于N / 2的话,说明mid太大了.以此为条件进行第一重二分搜索,第二重二分搜索是对X的搜索,直接用lower_bound实现. #include <iostream> #include <algorithm> #include <cstdio> #include <cmath&g

POJ 3685 Matrix 二分套二分

POJ 3685 Matrix 二分 题意 有一个N阶方阵,方正中第i行第j列的元素值为\(d_{i,j}=i^{2}+1e5*i+j^{2}-1e5*j+i*j\),我们需要找出这个方阵中第M小的元素值. 解题思路 分析这个公式,我们发现:当j固定的时候,这个公式关于i(取值范围:从0到n)是单调增加的,所以这里我们可以二分一个答案,然后一列一列的找小于(等于)它的个数,这样加起来我们就能知道我们枚举的这个答案是第几小了. 需要注意的是,第一个最外层的二分有点不同,因为我们二分的答案可能不存在

poj 2401 划分树 求区间第k大的数

题目:http://poj.org/problem?id=2104 划分树待我好好理解下再写个教程吧,觉得网上的内容一般,,, 模板题: 贴代码: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define CLR(a) memset(a,0,sizeof(a)) const int MAXN = 1000

leetcode | Median of Two Sorted Arrays 寻找2个有序数组中第k大的值

问题 Median of Two Sorted Arrays There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)). 分析 本题更经典通用的描述方式时: 给定2个有序数组,找出2个数组中所有元素中第k大的元素. 思路1 直观思

POJ 2985 The k-th Largest Group(树状数组 并查集/查找第k大的数)

传送门 The k-th Largest Group Time Limit: 2000MS   Memory Limit: 131072K Total Submissions: 8690   Accepted: 2847 Description Newman likes playing with cats. He possesses lots of cats in his home. Because the number of cats is really huge, Newman wants

【POJ】【2104】区间第K大

可持久化线段树 可持久化线段树是一种神奇的数据结构,它跟我们原来常用的线段树不同,它每次更新是不更改原来数据的,而是新开节点,维护它的历史版本,实现“可持久化”.(当然视情况也会有需要修改的时候) 可持久化线段树的应用有很多,仅以区间第K大这种简单的问题来介绍这种数据结构. 我们原本建立的线段树是表示区间的,或者说,维护的是[位置],存的是每个位置上的各种信息.它的优点是满足区间加法,但不满足区间减法,所以我们这里要换一种建树方式:对于每个区间[1,i]建立一棵权值线段树.这个线段树的作用其实就

poj 2349 Arctic Network(最小生成树的第k大边证明)

题目链接: http://poj.org/problem?id=2349 题目大意: 有n个警戒部队,现在要把这n个警戒部队编入一个通信网络, 有两种方式链接警戒部队:1,用卫星信道可以链接无穷远的部队. 2,用信号收发器可以链接周围d米以内的部队. 现在有s个卫星信道,问d最小是多少时能连接全部的警戒部队? 解题思路: 我是用求最小生成树,记录路径长度,对路径长度排序后,第k长的边就是答案, 但是队友是用最小k度限制生成树,因为我的方法它证明不了,也推翻不了~~~~, 最后我下去仔细想了想反证