WHY吃糖果 QDUOJ 二分嵌套

原题链接

解题思路参考链接

题意

给出一个\(n*n\)的矩阵，每个格子的权值为\(i*i+j*j+i*j+100000*(i-j)\)，求该矩阵中第m小的权值为多少

解题思路

当列数固定时，这个函数是随着行数的增加而增加的（二次函数简单判断下就行），于是外层的二分进行二分答案，里面的二分进行判断小于等于当前答案的格子有多少个。这样就可以解决问题。参考大佬的思路，可以点击查看。

代码实现

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll inf=0x3f3f3f3f3f3f3f3f;

ll n, m;

ll mul(ll i, ll j)

{

	return i*i+j*j+i*j+100000*(i-j);

}

ll judge(ll x)

{

	ll ret=0;

	for(ll j=1; j<=n; j++)

	{

		ll l=1, r=n, mid, tmp=0;

		while(l<=r)

		{

			mid=(l+r)>>1; //这是行数

			if(mul(mid, j) <= x)

			{

				tmp=mid;//在列数一定时，有多少个格子满足要求

				l=mid+1;

			}

			else

				r=mid-1;

		}

		ret+=tmp;//这里是所有的格子里面满足要求的格子数

	}

	return ret;

}

int main()

{

	int t;

	scanf("%d", &t);

	while(t--)

	{

		ll L=-inf, R=inf, ans, mid;

		cin>>n>>m;

		while(L<=R)

		{

			mid=(L+R)>>1;

			if(judge(mid) < m) //这里需要注意一下，没有等号

			{

				L=mid+1;

			}

			else

			{

				ans=mid;

				R=mid-1;

			}

		}

		printf("%lld\n", ans);

	}

	return 0;

 }

巴特西

WHY吃糖果 QDUOJ 二分嵌套

WHY吃糖果 QDUOJ 二分嵌套

题意

解题思路

代码实现

最新文章

热门文章