题解

将猴子分为三个集合：

• 集合 $A$：只想坐第 $1$ 排的 $a$ 只猴子。
• 集合 $B$：只想坐第 $2$ 排的 $b$ 只猴子。
• 集合 $C$：无偏好的 $c$ 只猴子。

教室有 $2$ 排，每排 $m$ 个座位。我们需要最大化坐下的猴子数量，且必须满足有偏好猴子的要求。

贪心策略的证明：

如果第 $1$ 排还有空位，并且集合 $A$ 中还有未安排的猴子，那么优先把集合 $A$ 的猴子安排到第 $1$ 排一定是最优的。原因在于：集合 $C$ 的猴子可以坐到任意一排，而集合 $A$ 的猴子只能坐第 $1$ 排。若我们优先用集合 $C$ 的猴子填充第 $1$ 排，可能导致第 $1$ 排被填满后，仍有集合 $A$ 的猴子无法入座，而此时第 $2$ 排也许还有空位，但这些空位对于集合 $A$ 的猴子是无用的。这样就会造成座位浪费，无法达到最大数量。对称地，对于第 $2$ 排和集合 $B$ 也是同样的道理。因此，全局最优的策略是：先尽可能满足有严格偏好的猴子，再用无偏好的猴子填充所有剩余座位。

算法步骤：

1. 将集合 $A$ 的猴子安排到第 $1$ 排，能坐下的数量为 $\min(m, a)$。
   第 $1$ 排剩余座位数为 $r_1 = m - \min(m, a)$。

2. 将集合 $B$ 的猴子安排到第 $2$ 排，能坐下的数量为 $\min(m, b)$。
   第 $2$ 排剩余座位数为 $r_2 = m - \min(m, b)$。

3. 此时两排共剩余座位数：

   $$rem = r_1 + r_2 = 2m - \min(m, a) - \min(m, b)$$

   这些剩余座位可以任意分配给集合 $C$ 的猴子，能坐下的数量为 $\min(rem, c)$。

4. 总答案即为三部分之和：

   $$ans = \min(m, a) + \min(m, b) + \min(rem, c)$$

时间复杂度： 每组测试数据只需 $O(1)$ 计算，总复杂度 $O(t)$，完全可以通过 $t \le 10^4$ 的数据范围。

C++ 参考代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    while(tt--)
    {
        int m,a,b,c;
        cin>>m>>a>>b>>c;
        int ans=0,rem=0;
        ans+=min(m,a); rem+=m-min(m,a);
        ans+=min(m,b); rem+=m-min(m,b);
        ans+=min(rem,c);
        cout<<ans<<'\n';
    }
    return 0;
}