POJ 3685 Matrix 题解 《挑战程序设计竞赛》

POJ 3685 Matrix

矩阵：N阶矩阵A_ij= i² + 100000 × i + j² – 100000 × j + i × j，求第M小的元素。

3.1不光是查找值！“二分搜索”

查找第k大的值

观察 i² + 100000 × i + j² – 100000 × j + i × j这个表达式，发现是对i递增的，于是利用这个特性进行二分搜索，统计比mid小的数的个数，接着以此个数是否小于M（小于的话说明mid太小了）进行外层的二分搜索。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
using namespace std;

typedef long long LL;
LL T, N, M;

LL f(const LL& i, const LL& j)
{
	return i * i + 100000 * i + j * j - 100000 * j + i * j;
}

// mid 是否小于第M小的数
bool is_less(const LL& mid)
{
	LL less_count = 0;	// 比mid小的数的个数
	for (int j = 1; j < N + 1; ++j)
	{
		// 当然不能这么搜啦
// 		for (int i = 1; i < N + 1; ++i)
// 		{
// 
// 		}
		int lb = 0, ub = N + 1;
		while (ub - lb > 1)
		{
			int i = (ub + lb) >> 1;
			if (f(i, j) < mid)
			{
				lb = i;
			}
			else
			{
				ub = i;
			}
		}
		less_count += lb;
	}

	return less_count < M;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> T;
	while (T--)
	{
		cin >> N >> M;
		LL lb = -100000 * N, ub = N * N + 100000 * N + N * N + N * N;
		while (ub - lb > 1)
		{
			LL mid = (ub + lb) >> 1;
			if (is_less(mid))
			{
				lb = mid;
			}
			else
			{
				ub = mid;
			}
		}
		cout << lb << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3685 Matrix 题解 《挑战程序设计竞赛》