石头、剪刀、布II

100分解法

首先这个问题有一个前置问题,就是最多能赢多少局。这个问题其实比较简单,只需要即可,很好理解。
但是现在不是问最多赢多少局了,问最多积多少分。这里就需要使用贪心的思想了,先把能赢的局全部赢下来。
为什么这样是合理的呢?我们这么反向考虑这个问题,比如我有一局能赢我选择不赢,那不赢最好的结果不过是这局变成平局,比如有4张卡片。牛牛有a,b;牛妹有c,d。牛牛a本来能赢牛妹的c,但牛牛的a现在跟牛妹的d打(代表随机的一次能赢的局不赢去交换),因为cd相同没有意义相当于没有交换所以c和d一定不同,也就是证明了这场在积分上来说最多不过是由胜局变平局。我们假设原来最差的情况是b会输给d,现在换成b和c打了,但是b也一定赢不了c。为什么呢?因为a能赢c,ab一定不相同(因为相同交换相当于没交换),所以最差情况不过是原来赢一局,输一局,变成了两个平局,对积分是没有影响的,非最差情况就更不会有负面影响了。所以反证法可得出每个能赢的局都先赢即可。
考虑赢下所有的能赢的局后,已经不存在能赢的局了,剩下只有平局和输两种情况,想要积分高显然让平局变多。所以此时令剩下的牌里。在这之后牛牛只剩p1+q1+m1张牌了,而现在既没有能打成平局的牌,也没有能赢的牌,所以也就是牛牛剩下的牌全会输。这时更新ans令,最后得到的ans即是答案。时间复杂度o(1),空间复杂度o(1)。
代码如下:
1.比较容易理解的代码写法:

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param p1 int整型 
     * @param q1 int整型 
     * @param m1 int整型 
     * @param p2 int整型 
     * @param q2 int整型 
     * @param m2 int整型 
     * @return int整型
     */
    int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        // write code here
        int ans=min(p1,q2)+min(q1,m2)+min(m1,p2);
        int x1=min(p1,q2);
        p1-=x1;
        q2-=x1;
        x1=min(q1,m2);
        q1-=x1;
        m2-=x1;
        x1=min(m1,p2);
        m1-=x1;
        p2-=x1;
        p1-=min(p1,p2);
        q1-=min(q1,q2);
        m1-=min(m1,m2);
        ans-=(p1+q1+m1);
        return ans;
    }
};

2.更易阅读的代码写法:

int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        // write code here
        int ret=0;
        int a[3]={p1,q1,m1},b[3]={p2,q2,m2};
        for(int i=0;i<3;i++)
            for(int j=-1;j<=1;j++)
            {
                int t=min(b[i],a[(i+j+3)%3]);
                ret-=j*t;
                b[i]-=t;
                a[(i+j+3)%3]-=t;
            }
        return ret;
    }
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务