http://codeforces.com/problemset/problem/546/C
题意:
总共有n张牌,1手中有k1张分别为:x1, x2, x3, ..xk1,2手中有k2张,分别为:y1, y2, ...yk2;(n<=10&&k1+k2==n,所有牌的数字都不同);
依次比较x1, y1的大小,若x1>y1,依次将x1, y1加入x牌最底下;反之则将y1,x1依次加入y牌最底下;直至有方的牌输完为止;输出总共游戏的步数和赢方;
如果两方都不能赢,则输出-1;
思路:直接用栈模拟,关键的地方是判断两方都不能赢的情况,判断方法有两种:
其一是设一个足够大的数,超过这个步数还没有分出输赢情况的话则可以认定
两方都不能赢,因为n<=10,如果能分出输赢的话则500步以内一定会出结果的!
另一种方法是判断当前状态之前是否出现过,若出现过,则其一定不能分出输赢!会死循环!
至于如何判断是否出现过,可以将每个状态都存入一个string数组中,再将当当前状态与之对比,若出现过,则平局;
代码分别如下:
方法1:
#include<bits/stdc++.h>
#define MAXN 10000
#define MAX 1000000000
#define eps 1e-6
#define ll long long
using namespace std; int main(void)
{
queue<int> stk1, stk2;
string str1[MAXN], str2[MAXN];
int n, a, b, ans=;
cin >> n;
cin >> a;
for(int i=; i<a; i++)
{
int x;
cin >> x;
stk1.push(x);
}
cin >> b;
for(int i=; i<b; i++)
{
int x;
cin >> x;
stk2.push(x);
}
int cnt=, flag;
while()
{
int x=stk1.front(), y=stk2.front();
if(x>y) //****如果x>y,将y, x依次从队尾加入stk1队列,并将stk2,stk1队首元素y, x抛掉;
{
stk1.push(y);
stk1.push(x);
stk1.pop();
stk2.pop();
}
else //****如果x<y,将x, y依次从队尾加入stk2队列,并将stk2, stk1队首元素y, x抛掉;
{
stk2.push(x);
stk2.push(y);
stk2.pop();
stk1.pop();
}
cnt++;
if(stk1.empty()) //****队列stk1为空,即2赢了
{
cout << cnt << " " << "" << endl;
return ;
}
if(stk2.empty()) //****队列stk2为空,即1赢了
{
cout << cnt << " " << "" << endl;
return ;
}
if(cnt>) break; //****如果步数大于500还没分输赢,即可判平局
}
cout << "-1" << endl;
return ;
}
方法2:
#include<bits/stdc++.h>
#define MAXN 10000
#define MAX 1000000000
#define eps 1e-6
#define ll long long
using namespace std; int main(void)
{
queue<int> stk1, stk2;
string str1[MAXN], str2[MAXN];
int n, a, b, ans=;
cin >> n;
cin >> a;
for(int i=; i<a; i++)
{
int x;
cin >> x;
stk1.push(x);
}
cin >> b;
for(int i=; i<b; i++)
{
int x;
cin >> x;
stk2.push(x);
}
int cnt=, flag;
while()
{
int low1[MAXN], low2[MAXN], k1=, k2=;
while(!stk1.empty()) //**将stk1存入string数组中
{
low1[k1++]=stk1.front();
stk1.pop();
}
for(int i=; i<k1; i++)
{
stk1.push(low1[i]);
}
for(int i=; i<k1; i++)
{
str1[cnt]+=to_string(low1[i]);
}
while(!stk2.empty()) //****将stk2存入string数组中
{
low2[k2++]=stk2.front();
stk2.pop();
}
for(int i=; i<k2; i++)
{
stk2.push(low2[i]);
}
for(int i=; i<k2; i++)
{
str2[cnt]+=to_string(low2[i]);
}
for(int i=; i<cnt; i++) //***判断当前状态是否出现过,若出现过,则平局
{
if(str1[i]==str1[cnt]&&str2[i]==str2[cnt])
{
cout << "-1" << endl;
return ;
}
}
int x=stk1.front(), y=stk2.front();
if(x>y) //****如果x>y,将y, x依次从队尾加入stk1队列,并将stk2,stk1队首元素y, x抛掉;
{
stk1.push(y);
stk1.push(x);
stk1.pop();
stk2.pop();
}
else //****如果x<y,将x, y依次从队尾加入stk2队列,并将stk2, stk1队首元素y, x抛掉;
{
stk2.push(x);
stk2.push(y);
stk2.pop();
stk1.pop();
}
cnt++;
if(stk1.empty()) //****队列stk1为空,即2赢了
{
flag=;
break;
}
if(stk2.empty()) //****队列stk2为空,即1赢了
{
flag=;
break;
}
}
cout << cnt << " " << flag << endl;
return ;
}