自动搬运

查看原文

来自洛谷，原作者为

	Terrible 没错，这家伙还真的是很懒惰，真的什么都没留下！！

搬运于2025-08-24 22:27:21，当前版本为作者最后更新于2021-02-07 22:50:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

观前提醒

表述略有些啰嗦，请先浏览一遍，找到有用的东西，懂怎么做就行了。

题目简述

• Mirco 把最小的数据变成第二小的数据；
• Slavko 把最大的数据变成第二大的数据；
• 就是把数据从两边往中间挤。
• 两人轮番，直到只剩下两种大小的数据，留下的烂摊子是谁的，谁就输了。
• 输出赢的人和这两个数据大小（也可能是一种）。
• 如果游戏开局就两种甚至一种长度的麦秆，Mirco 就直接输掉了。

思路

暴力模拟程序呼之欲出，排个序模拟一下就行，不过暴力打出来程序几乎是 $O(n^2)$（跟滚雪球一样，中间数据越滚越多），一看 $1 \leq n \leq 10^5$，会妥妥地 T 掉，所以需要优化一下。

由于我们只关注麦秆的相对大小，那么就可以进行排序然后离散化处理，然后把相同数据归并，然后把数据往中间挤，记录操作者就行。所以主体的时间复杂度是 $O(n \log n)$（排序的复杂度）和 $O(n)$（挤数据的复杂度）。

思路演练

例如（手写数据）：

12
3 24 341 231 342 443 543 3 4 4 2 743

排序：

2 3 3 4 4 24 231 341 342 443 543 743

离散化处理后归并：

上图，

①蓝色状态表示有 $4$ 组以上数据，两人完成整轮整轮的操作，让两端有一组或两组完全被“挤”到中间，操作过程中不触发游戏结束机制，操作完仍然该 Mirko 操作。

②黄色状态表示 $3$ 组数据，有结束游戏的可能，具体展示了谁会输。

③红色状态就表明游戏结束。

输出：

Mirko
231 341

代码

#include<cstdio>
#include<algorithm>
int read()//正整数快读 
{
	int a=0;char c;
	while((c=getchar())<'0');
	while(c>='0')a=a*10+(c^48),c=getchar();
	return a;
}
int source[100003]/*源数据*/,mapping[100003]/*反向映射*/;//离散化
int bucket[100003]/*桶装数据*/,min,max;//归并数据 
int main()
{
	int n=read(),cnt=1;
	for(int i=1;i<=n;i++)source[i]=read();
	std::sort(source+1,source+n+1);//排序 
	for(int i=1;i<=n;i++)//离散化 归并数据 
	{
		mapping[cnt]=source[i],bucket[cnt]++;
		if(source[i]<source[i+1])cnt++;
	}
	int min=1,max=cnt;//找到边界往中间挤 
	while(max-min>=3)//max-min+1>=4 “挤”数据要保证至少有4个，否则需要考虑先后手交换 
	{
		//两人转移相同数目的数据，且转移过程中不触发游戏结束机制，下次的操作者不变 
		int m=std::min(bucket[min],bucket[max]);
		bucket[max-1]+=m,bucket[max]-=m;
		bucket[min+1]+=m,bucket[min]-=m;
		if(!bucket[min])min++;
		if(!bucket[max])max--;
	}
	bool f=1;//0表示Mirko胜利，1表示该Slavko胜利 
	//先赋值1，如果max-min+1<=2 Slavko直接胜利 
	if(max-min>=2)//max-min+1>=3 这里判别输赢问题 
	{
		//显然，左端数据如果小于等于右端数据，由于Mirko是先手，甩锅，输局留给对方
		 if(bucket[min]<=bucket[max])f=0,min++;
		 else max--;
	}
	printf("%s\n%d %d",!f?"Mirko":"Slavko",mapping[min],mapping[max]);
}

特别解释：

例如，若上面程序中 $bucket$ 剩下四组数据：$3$ $2$ $1$ $3$，两人同时向中间转移数据，转移完成就成了 $5$ $4$，游戏结束，不过我们可以认为转移过程中是没有结束游戏的，转移完成了才结束游戏，所以下一次仍然是 Mirko，直接接受败局！

再例如，上面程序中 $bucket$ 剩下三组数据：$3$ $2$ $3$，转移数据的过程中就结束游戏了，所以轮不完 $3$ 轮游戏，到 $1$ $5$ $1$ 时，Mirko 把小数据往右挤，成了 $6$ $2$，那么 Slavko 就要接受败局。