题目描述
老六和老七都是有名的美食家，你则是有名的大厨，你的任务是想办法让他们尽可能地多吃你做的菜。
一开始，老六和老七的开心度为0，如果某位美食家喜欢这道菜，那他的开心度+1，如果不喜欢，那他的开心度-1.
你一道道地上菜，你上一盘，老六和老七尝一盘，一旦有某个美食家开心度 < 0，那你就不能继续上菜了。
你提前准备好了 a + b + c + d 盘菜，代表：
- 老六喜欢，老七也喜欢的菜有a盘；
- 老六喜欢，老七不喜欢的菜有b盘；
- 老六不喜欢，老七喜欢的菜有c盘；
- 老六不喜欢，老七不喜欢的菜有d盘；
可以知道上菜顺序不一样，最终吃的盘数也可能不一样。请输出在最优的安排下你最多能上几盘菜。
输入格式
第一行一个整数 t 表示数据组数。
对于每组数据，一行四个整数 a b c d。
输出格式
对于每组数据一个整数表示你最多能上几盘菜。
样例输入
4
5 0 0 0
0 0 0 5
2 5 10 6
3 0 0 7
样例输出
5
1
15
7
约定
1\le t\le10^4
0\le a_1,a_2,a_3,a_4\le10^8
a_1+a_2+a_3+a_4\ge1
1 个赞
叶宸铄
(叶宸铄)
2
问题分析
我们有四类菜品：
- a: 老六和老七都喜欢的菜，吃了后他们的开心度都增加。
- b: 老六喜欢，老七不喜欢的菜，吃了后老六的开心度增加，老七的开心度减少。
- c: 老六不喜欢，老七喜欢的菜，吃了后老六的开心度减少，老七的开心度增加。
- d: 老六和老七都不喜欢的菜，吃了后他们的开心度都会减少。
我们需要通过合理的顺序安排，保证在尽可能多的菜品下，上菜时没有任何一个美食家的开心度变为负数。只要有一个美食家的开心度变为负数，我们就不能再继续上菜。
解决思路
- 优先考虑正向影响的菜：
- a类菜品（老六和老七都喜欢的）是最安全的，因为它们对两人都有正向影响，吃了它们肯定不会导致任何一个人的开心度变负。
- 接下来是b类和c类菜品。b类菜品虽然老六喜欢，但是会让老七不高兴，c类菜品则是反过来的。我们需要小心地选择它们的上菜顺序。
- 最后是d类菜品，它们对两个人都有负向影响，必须谨慎地安排。
- 最优策略：
- 先上a类菜，因为它们不会引起任何负面影响。
- 接着上b类和c类菜，但要小心顺序。我们要尽量让一方的开心度始终保持非负值。
- 最后才上d类菜，如果我们发现两个美食家都不高兴时，才考虑这些菜。
- 具体操作：
- 上完所有a类菜后，再依次考虑b类和c类菜，确保不让任何一个人的开心度变负。
- 最后尝试上d类菜，并确保它们不会导致开心度变负。
解法步骤
- 遍历所有菜品的类型：
- 先上a类菜，增加两个人的开心度。
- 然后在剩余的菜品中，优先选择那些对开心度影响小的菜（尽量少用d类菜，避免两人都变负）。
- 确保美食家的开心度始终非负。
1 个赞