石头、剪刀、布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;
}
OPPO公司福利 1202人发布