题意:
Alice有张石头牌、张剪刀牌、张布牌,
Bob有张石头牌、张剪刀牌、张布牌,
其中获胜得1分,平局不得分也不扣分,失败扣1分。
你可以随意安排出牌策略,问Alice最多可以得多少分?(可能是负数)
解法一(暴力模拟)
我们按照『能获胜就获胜,不能获胜就平局,实在不行才失败』这样一个贪心策略来,显然这样得分一定是最高的。
一. 我们首先考虑获胜的情况
1. Alice出石头,Bob出剪刀。
2. Alice出剪刀,Bob出布。
3. Alice出布,Bob出石头。
故当都不为0时,我们每次让同时减一,然后答案加一。
当都不为0时,我们每次让同时减一,然后答案加一。
当都不为0时,我们每次让同时减一,然后答案加一。
二. 我们接着考虑平局的情况
1. Alice出石头,Bob出石头。
2. Alice出剪刀,Bob出剪刀。
3. Alice出布,Bob出布。
故当都不为0时,我们每次让同时减一。
当都不为0时,我们每次让同时减一。
当都不为0时,我们每次让同时减一。
三. 最后考虑失败的情况
由于只有获胜、平局、失败三种情况,其中获胜和平局两种情况的牌在前面已经出完了,故Alice剩下出的牌一定是失败的。
故答案减即可。
代码:
class Solution { public: int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) { int ans=0; //胜利的 while(p1>0&&q2>0){//石头胜剪刀 ans++;//答案+1 p1--,q2--;//两个牌的数量分别减一 } while(q1>0&&m2>0){//剪刀胜布 ans++;//答案+1 q1--,m2--; } while(m1>0&&p2>0){//布胜石头 ans++; m1--,p2--; } //平局的 while(p1>0&&p2>0){//石头对石头 p1--,p2--; } while(q1>0&&q2>0){//剪刀对剪刀 q1--,q2--; } while(m1>0&&m2>0){//布对布 m1--,m2--; } //失败的 //Alice出剩下的牌一定会失败,故直接减去即可 ans-=p1+q1+m1; return ans; } };时间复杂度:,最坏情况Alice出的所有牌都要在while循环中完成,总共有张牌,故时间复杂度为
空间复杂度:,程序中没有申请额外的空间,故空间复杂度为
解法二(直接计算)
我们首先考虑Alice获胜的情况:
假设Alice出石头,Bob出剪刀
1.
显然这种情况获胜次数为,得分为
2.
显然这种情况获胜次数为或,得分也为或
3.
显然这种情况获胜次数为,得分也为
综上所述,这种情况的得分为
其他两种获胜的情况同理,得分分别为和
我们接下来在考虑平局和失败两种情况时,首先应该将Alice和Bob消耗的牌数量给减掉,即:
和减去
和减去
和减去
我们接下来考虑平局的情况:
1. Alice出石头,Bob出石头:显然平局次数为
2. Alice出剪刀,Bob出剪刀:显然平局次数为
3. Alice出布,Bob出布:显然平局次数为
接下来将平局情况消耗的牌数量减掉,即:
和减去
和减去
和减去
最后失败的情况同解法一,即答案减去即可
代码:
class Solution { public: int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) { int ans=0;//最后得分 int t=min(p1,q2);//石头对剪刀 ans+=t;//获胜次数 p1-=t,q2-=t;//减去获胜消耗的牌 t=min(q1,m2);//剪刀对布 ans+=t;//获胜次数 q1-=t,m2-=t;//减去获胜消耗的牌 t=min(m1,p2);//布对石头 ans+=t;//获胜次数 m1-=t,p2-=t;//减去获胜消耗的牌 t=min(p1,p2);//石头对石头 p1-=t,p2-=t;//减去平局消耗的牌 t=min(q1,q2);//剪刀对剪刀 q1-=t,q2-=t;//减去平局消耗的牌 t=min(m1,m2);//布对布 m1-=t,m2-=t;//减去平局消耗的牌 ans-=p1+q1+m1;//最后出的牌一定是失败的,答案减去牌的数量即可 return ans; } };时间复杂度:,min函数的时间复杂度是的,程序只调用了级别次数min函数和级别次加减法运算,故总的时间复杂度为
空间复杂度:,程序没有申请额外的空间,故空间复杂度为