自动搬运

查看原文

来自洛谷，原作者为

	zymooll 这个B . . . . . . . . . . 站用户很菜，什么也没有留下

搬运于2025-08-24 22:42:57，当前版本为作者最后更新于2022-11-11 13:14:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

当时写传智杯这道题的时候就是奔着写题解来的，但是一直没开，今天中午（2022-11-11 12:50）恰巧看见加入主题库了，便赶来写一写。

题意简述

模拟三个人按 1,2,3,1,2,3,1... 顺序出牌，每次每人出牌遵守恰好打出在自己所有可以打（即比上家大）的牌型中最小的牌，若无合法牌型可出，则本轮不出牌。

若有人出牌后，其余两人都不出牌（即要不起），则从该人开始开始下一轮，该人打出本人最小的牌型。

合法的牌型由 $N$ 张点数相同的牌构成。

牌的大小决定与牌型的长度（$len$）和其中的点数（$N$）决定：

对于牌型 $A$ 和 $B$，若 $len_A>len_B$，则 $A$ 大，反之则 $B$ 大。

特殊的，若 $len_A=len_B$ 时，比较构成 $A$ 和 $B$ 的数字 $N_A$ 和 $N_B$，若 $N_A > N_B$ 时，则 $A$ 大；若 $N_A = N_B$ 时，则一样大；若 $N_A < N_B$ 时，则 $B$ 大。

算法简述

本题我们采用模拟算法。通过模拟每个人的出牌，出牌后检查其牌是否打光判断胜负。

具体实现请查阅代码。

可行性证明

模拟题就不说这个了吧。。。

时间复杂度及空间复杂度

时间复杂度：最坏 $O(3n)$

空间复杂度：$O(nm)$

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ls,js,mjs;
int a[10][60];//a[第几个人][哪种牌]->有几张
int b[10];//统计每个人打了几张牌 用来判断获胜 
struct p{int x,n;/*x=牌型 n=数量*/}s,mins;//上家打的什么牌 不要为0 1
int main(){
	s.x=0;s.n=1;
	cin>>n>>m;
	for(int i=1;i<=3;i++){
		for(int j=0;j<n;j++){
			cin>>ls;
			a[i][ls]++;
		}
	}
	while(1){//控制每轮 
		for(int i=1;i<=3;i++){//模拟每个人 
			//cout<<i<<":";
			mins.x=INT_MAX;mins.n=INT_MAX;
			for(int j=1;j<=m;j++){//模拟打哪种 
				if(a[i][j]>s.n){//比上家牌多  
					if(j<=s.x){
						if(s.n+1<mins.n||(s.n+1==mins.n&&j<mins.x)){
							mins.n=s.n+1;mins.x=j;
						}
					}
					else{
						if(s.n<mins.n||(s.n==mins.n&&j<mins.x)){
							mins.n=s.n;mins.x=j;
						}
					}
				}
				if(a[i][j]==s.n&&j>s.x){//跟上家牌一样 但是我比他大 
					if(s.n<mins.n||(s.n==mins.n&&j<mins.x)){
						mins.n=s.n;mins.x=j;
					}
				}
			}
			if(mins.x==INT_MAX){
				mjs++;
				//cout<<endl;
				if(mjs==2){
					s.x=0;s.n=1;
					mjs=0;
				}
				continue;
			}
			else mjs=0;
			//for(int j=0;j<mins.n;j++)cout<<mins.x;
			//cout<<endl;
			a[i][mins.x]-=mins.n;
			b[i]+=mins.n;
			s.x=mins.x;s.n=mins.n;
			if(b[i]==n){
				cout<<i;
				return 0;
			}
			
		}
	}
	return 0;
}

备注

这个代码是一年半之前写的，写的不好多多见谅，更新的代码会放在这里 Link，有任何疑问也欢迎发私信。