2020-10-23
感觉有趣的思维题用高大尚的算法解决掉会很无趣qwq , 给出一个不一样的贪心思路。
题目中给了一个最重要的条件
→
a
1
+
a
2
+
a
3
=
b
1
+
b
2
+
b
3
\rightarrow a_1 + a_2 + a_ 3 = b_1 + b_2 + b_3
→a1+a2+a3=b1+b2+b3
对于最大胜场很好考虑
a
n
s
=
m
i
n
(
a
1
,
b
2
)
+
m
i
n
(
a
2
,
b
3
)
+
m
i
n
(
a
3
,
b
1
)
ans = min (a_1 , b_2) + min (a_2 , b_3) + min (a_3 , b_1)
ans=min(a1,b2)+min(a2,b3)+min(a3,b1)
对于最少胜场 , 有一个很重要的结论 , 那就是答案只含有(石头剪子布)中的最大的一个贡献 , 也就是说不会出现石头有胜场 , 剪刀也有胜场的情况。
为什么呢 ? 对于石头的贡献是
a
1
−
b
1
−
b
3
a_1 -b_1-b_3
a1−b1−b3 , 若✂也有贡献那贡献之和就是
a
1
+
a
2
−
b
1
−
b
3
−
b
2
a_1 + a_2 - b_1 - b_3 - b_2
a1+a2−b1−b3−b2 若有贡献 , 也就是大于0 , 便不满足题目给出的条件。
那最少胜场答案也就是石头剪子布中贡献最大的那一个。
代码:
int a1 , a2 , a3 , b1 , b2 , b3 , n ;
scanf ("%d%d%d%d%d%d%d" , &n , &a1 , &a2 , &a3 , &b1 , &b2 , &b3) ;
printf ("%d %d" , max (0 , max (a1 - b1 - b3 , max (a2 - b2 - b1 , a3 - b3 - b2))) , min (a1 , b2) + min (a2 , b3) + min (a3 , b1)) ;
本文地址:https://blog.csdn.net/spoo_ki/article/details/109245649