共42道题，当前是第5题

初赛真题

田忌赛马，田忌每赢一次齐王的马就得 $200$ 金币，当然输了就扣 $200$ 金币，平局则金币数不变。 

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	while (cin >> n && n != 0) {
		int tj[1001], king[1001], count = 0;
		int tj_min = 0, tj_max = n - 1;
		int king_min = 0, king_max = n - 1;
		for (int i = 0; i < n; i++) cin >> tj[i];
		for (int i = 0; i < n; i++) cin >> king[i];
		sort(tj, tj + n);
		sort(king, king + n);
		while (n--) {
			if (tj[___(1)___] > king[___(2)___]) {
				count++;
				tj_max--;
				king_max--;
			} else if (tj[___(3)___] < king[___(4)___]) {
				count--;
				tj_min++;
				king_max--;
			} else {
				if (tj[tj_min] > king[king_min]) {
					count++;
					___(5)___;
					___(6)___;
				} else {
					if (___(7)___)
						count--;
					tj_min++;
					___(8)___;
				}
			}
		}
		cout << count * 200 << endl;
	}
	return 0;
}

1. A。
2. C。
3. A。
4. A。
5. B。

这道题主要是对田忌赛马的贪心策略的实现，策略如下：
1. 如果田忌最快的马能够跑赢齐王最快的马，那么就让这两只马跑。
2. 在 $1$ 不成立时，如果田忌最差的马会输给齐王最差的马，就用这最差的马换掉齐王最好的马
3. 在 $2$ 不成立时，如果田忌最差的马能赢齐王最差的马，那就跑
4. 在 $3$ 不成立时，此时两匹最差的马实力相当，则用田忌最差的马换掉齐王最好的马

Question

1. (1) 和 (2) 处填（ ）

2. (3) 和 (4) 处填（ ）

3. (5) 和 (6) 处填（ ）

4. (7) 处填（ ）

5. (8) 处填（ ）

陈伦制作 版权所无 粤ICP备16127491号-1