题解 P7175 【[COCI2014-2015#4]PŠENICA】
观前提醒
表述略有些啰嗦，请先浏览一遍，找到有用的东西，懂怎么做就行了。
题目简述
- Mirco 把最小的数据变成第二小的数据；
- Slavko 把最大的数据变成第二大的数据；
- 就是把数据从两边往中间挤。
- 两人轮番，直到只剩下两种大小的数据，留下的烂摊子是谁的，谁就输了。
- 输出赢的人和这两个数据大小（也可能是一种）。
- 如果游戏开局就两种甚至一种长度的麦秆，Mirco 就直接输掉了。
思路
暴力模拟程序呼之欲出，排个序模拟一下就行，不过暴力打出来程序几乎是
由于我们只关注麦秆的相对大小，那么就可以进行排序然后离散化处理，然后把相同数据归并，然后把数据往中间挤，记录操作者就行。所以主体的时间复杂度是
思路演练
例如（手写数据）：
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离散化处理后归并：
| i | 1(2) | 2(3) | 3(4) | 4(24) | 5(231) |
|---|---|---|---|---|---|
| b[i] | 1 | 2 | 2 | 1 | 1 |
| i | 6(341) | 7(342) | 8(443) | 9(543) | 10(743) |
| b[i] | 1 | 1 | 1 | 1 | 1 |
上图，
①蓝色状态表示有
②黄色状态表示
③红色状态就表明游戏结束。
输出：
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]);
}特别解释：
例如，若上面程序中
再例如，上面程序中