洛谷 P7579 「RdOI R2」称重(weigh) 题解

题意：

题目

一道交互题。

有 n 个球，里面有两个假球，假球比普通球的要轻，每次可以询问任意两组球的轻重关系，第一组轻为 < ,第二组轻为 > ,一样重量为 = 。

思路：

先考虑在一个区间内找 1 个假球。

我们可以将区间尽量平均分为 3 份，先询问相等的两组球的轻重关系，分 3 种情况：

• 第一组轻

由于在区间里只有 1 个假球，且区间长度一定，所以这个假球一定在第一组里，所以继续在第一组寻找 1 个假球。

• 第二组轻

与第一种情况一样，假球一定在第二组里，所以继续在第二组寻找 1 个假球。

• 一样重

因为只有一个假球，所以这个假球一定不在这两组里（否则一定会有一组轻），那么假球就一定在剩下的那组里，在剩下的那组寻找 1 个假球。

1 个假球的情况解决了，2 个假球呢？

我们先将区间平均分成 2 份，根据区间长度分为 2 种情况。

• 区间长度为偶数

询问平均分成的两段区间，和上面类似，也是 3 种情况。

1. 第一组轻

因为有 2 个假球，且区间长度一定，想让第一组轻，2 个假球都得在第一组里，所以在第一组继续寻找两个假球。

2. 第二组轻

与第一种情况类似，2 个假球一定都在第二组里，所以在第二组继续寻找两个假球。

3. 一样重

因为有两个球，既然一样重，那就一边一个，分别在两组中寻找一个假球。

• 区间长度为奇数

因为是奇数，所以一定会有一个球不在两个区间内（被单独拿出来），我们还是先询问两端均等的区间，依旧是三种情况：

1. 第一组轻

与偶数中的情况类似，第一组一定有假球，现在的问题就是剩下的那个球是不是假球。

我们可以换一个角度考虑，如果想确定第一个球是不是假球，最好的办法就是拿个真的和他比，但是我么如何找真的呢？

通过上面的研究，我们发现，假球一定在第一组和中间那个，剩下的第二组里一定都是真球。因此，直接将第二组拿出一个与剩下的那个球询问。相等则 2 个假的都在第一组，否则剩下的是个假的，第一组有 1 个假的。

2. 第二组轻

和第一组轻的情况一样，通过从第一组拿出球与剩下的那个比较。相等则 2 个假的在第二组，反之 1 个假的在第一组，1 个是剩下的那个球。

3. 一样重

由于一样重，所以剩下的那个不可能是假球（否则一、二两组中只有一个假的，且球数一样，无论在哪组都不可能一样重）。

这样，就又回到了偶数的情况，两个假的一边一个。

代码

请勿抄袭

#include<bits/stdc++.h>
using namespace std;
int jia1,jia2;//jia1和jia2表示两个假球的编号 
char ask(int l1,int r1,int l2,int r2)//询问l1~r1与l2~r2之间球的轻重关系。 
{
	printf("1 ");
	printf("%d ",r1-l1+1);//长度 
	for(int i=l1;i<=r1;i++) printf("%d ",i);
	printf("%d ",r2-l2+1);
	for(int i=l2;i<=r2;i++) printf("%d ",i);
	printf("\n");
	char ch; 
	cin>>ch;
	return ch;//读入并返回轻重关系 
}
void print()//输出结果 
{
	if(jia1>jia2) swap(jia1,jia2);//保证先输出的小 
	printf("2 %d %d\n",jia1,jia2);
	exit(0);//直接结束程序 
}
void make_ans(int ans)//将ans设为假球 
{
	if(!jia1) jia1=ans;
	else jia2=ans,print();
}
void find(int l,int r,int num)//l，r该次寻找区间的左右端点，num该区间中假球的数量 
{
	if(l==r)//找的只有一个球，这个球一定是假的 
	{
		make_ans(l);
		return;
	} 
	if(num==1)//找一个假球的情况 
	{
		int midl=l+(r-l)/3;//区间分为三份 
		int midr=r-(r-l)/3;
		char op=ask(l,midl,midr,r);//询问 
		if(op=='=')//相等，假期在剩下那组 
		{
			find(midl+1,midr-1,1);
		}
		if(op=='<')//否则在轻的那组 
		{
			find(l,midl,1);
		}
		if(op=='>')
		{
			find(midr,r,1);
		} 
	} 
	else//找两个假球的情况 
	{
		int mid=(l+r)/2;//先把区间分成二份		
		if((r-l+1)%2==0)//区间长度为偶数的情况 
		{
			char op=ask(l,mid,mid+1,r);//询问
			//以下为题解中的三种情况 
			if(op=='=')
			{
				find(l,mid,1);
				find(mid+1,r,1);
			}
			if(op=='<')
			{
				find(l,mid,2); 
			}
			if(op=='>')
			{
				find(mid+1,r,2);
			}
		}
		else//区间长度为奇数的情况 
		{ 
			char op=ask(l,mid-1,mid+1,r);//询问
			//三种情况 
			if(op=='=')
			{
				find(l,mid-1,1);
				find(mid+1,r,1);
			}
			if(op=='<')
			{
				char opt=ask(mid,mid,mid+1,mid+1);
				//右边（第二组）的球都是真的，利用询问得出剩下的那个是否为假球 
				if(opt=='=')//相等，不是假球 
				{
					find(l,mid-1,2);
				}
				else//不相等，是假球 
				{
					make_ans(mid);
					find(l,mid-1,1);					
				}
			}
			if(op=='>')
			{
				char opt=ask(mid,mid,mid-1,mid-1);
				if(opt=='=')
				{
					find(mid+1,r,2);
				}
				else
				{
					make_ans(mid);
					find(mid+1,r,1);					
				}
			}
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	find(1,n,2);//根据题意，在n个球中找两个假球 
}

写题解不易，点个赞呗