2309. 部落卡牌角斗场
1000ms
256MB
简单
枚举算法
题目描述
小新和大古在玩一个卡牌对战游戏。两人各有 $n$ 张牌，每张牌都有一个攻击力。游戏进行 $n$ 轮，每轮双方各出一张牌。
- 若小新的牌攻击力大于大古，小新得 200 分；
- 若小于大古，小新扣 200 分；
- 若相等，则双方均得 0 分。
已知两人的所有手牌，且小新可以自由安排每轮双方出牌的配对顺序。请计算小新能获得的最高得分。
输入格式
- 第一行包含一个正整数 $n$ ($1 \le n \le 1000$)，表示手牌数量。
- 第二行包含 $n$ 个正整数，表示小新的手牌攻击力。
- 第三行包含 $n$ 个正整数，表示大古的手牌攻击力。
输出格式
- 输出一个整数，表示小新最多能获得的得分。
样例 1
输入 (Input)
3 2 2 3 2 1 3
输出 (Output)
200
- 对于所有数据：$1 \le n \le 1000$，卡牌攻击力 $v_i$ 满足 $1 \le v_i \le 10000$。
- **样例解释**：
大古的手牌排序后为 `1 2 3`，小新的手牌为 `2 2 3`。
最优对阵策略为：
- 小新用 `2` 赢大古的 `1`（小新 +200 分）
- 小新用另一个 `2` 输给大古的 `3`（小新 -200 分）
- 小新用 `3` 赢大古的 `2`（小新 +200 分）
- 最终总得分为 $200 - 200 + 200 = 200$。
- **算法提示**：本题是经典的**田忌赛马**策略。将两人的手牌均从小到大排序，维护两人的最弱牌和最强牌指针：
1. 如果小新的最强牌大于大古的最强牌，直接用最强牌吃掉对方最强牌；
2. 如果小新的最弱牌大于大古的最弱牌，用最弱牌吃掉对方最弱牌；
3. 否则，用小新的最弱牌去消耗大古的最强牌（注意判断是否会扣分）。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功