WHY吃糖果 QDUOJ 二分嵌套

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
", ans);
	}
	return 0;
 }