放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

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

目录

POJ 3685 Matrix

矩阵:N阶矩阵Aij= i2 + 100000 × i + j2 – 100000 × j + i × j,求第M小的元素。

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

查找第k大的值

观察 i2 + 100000 × i + j2 – 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//////////////////////////////////
12843163 hankcs 3685 Accepted 216K 907MS C++ 1331B 2014-05-06 00:01:55

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机